A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes

Abstract

This article presents an algorithmic improvement to Sudan's (see J. Complexity, vol.13, p.180-93, 1997) list-decoding algorithm for Reed-Solomon codes and its generalization to algebraic-geometric codes from Shokrollahi and Wasserman (see ibid., vol.45, p.432-37, 1999). Instead of completely factoring the interpolation polynomial over the function field of the curve, we compute sufficiently many coefficients of a Hensel development to reconstruct the functions that correspond to codewords. We prove that these Hensel developments can be found efficiently using Newton's method. We also describe the algorithm in the special case of Reed-Solomon codes.