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

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