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

In [J. Complexity 13, 180-193 (1997; Zbl 0872.68026)], \textit{M. Sudan} described an algorithm for list-decoding of Reed-Solomon codes. A generalization to list-decoding of algebraic geometry codes appeared in [\textit{M. A. Shokrollahi} and \textit{H. Wassserman}, IEEE Trans. Inf. Theory 45, 432-437 (1999; Zbl 0947.94024)]. One of the steps of the algorithm involves finding all linear factors of the form \(y-f(x)\) of a given bivariate polynomial \(G(x,y)\). The authors describe a method for avoiding finding linear factors based on Hensel-lifting techniques.NEWLINENEWLINENEWLINEIt is claimed that for a Reed-Solomon code of length \(n\), \(O(n^2\log n)\) operations in \(\mathbb{F}_q\) are sufficient. The randomized factorization algorithm in [\textit{R. M. Roth} and \textit{G. Ruckenstein}, ibid. 46, 246-257 (2000; Zbl 1001.94046)] has a complexity of \(O(Lk\log^2 L(L\cdot\log Q+ n))\), where \(L\) is the maximal \(y\)-degree in \(G\).NEWLINENEWLINENEWLINEIt must be mentioned that the method from the present paper cannot be applied to the more general algorithm of \textit{M. Sudan} and \textit{V. Guruswami} [ibid. 45, 1757-1767 (1999; Zbl 0958.94036)] that handles higher multiplicities with interpolation. The algorithm of Roth and Ruckenstein [loc. cit.] can be used in this situation as well.