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' - n'(n' - t - 1)~(1/2) where n' = n(q - 1)/q, assuming t + 1 ≤ n'. In the typical case that qn/t ∈ (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 n)/lg lg n); and n~(O(1) bit operations for w≤ J' + O((lg n)/lg lg n).