Simplified high-speed high-distance list decoding for alternant codes

This paper presents a simplified list-decoding algorithm to correct any number w of errors in any alternant code of any length n with any designed distance t+1 over any finite field F_q ; in particular, in the classical Goppa codes used in the McEliece and Niederreiter public-key cryptosystems. The algorithm is efficient for w close to, and in many cases slightly beyond, the F_q Johnson bound J'=n' - sqrt{n'(n'-t-1)} where n'¿=¿n(q-1)/q, assuming t+1¿=¿n'. In the typical case that qn/t in (lg n)^O(1) and that the parent field has (lg n)^O(1) bits, the algorithm uses n(lg n)^O(1) bit operations for w = J' - n/(lg n)^O(1); O(n^ 4.5) bit operations for w = J' + o((lg lg n); and n^O(1) bit operations for w = J' + O((lgn)/lg lg n)