Power error locating pairs (Q782853)

For many practical applications to data storage or transmission, some of the more widely used error-correcting codes are the Reed-Solomon codes. Hence, efficient decoding algorithms for these codes, such as the Welch-Berlekamp algorithm that can correct up to half the minimum distance for Reed-Solomon codes, are always welcome. For many theoretical developments, algebraic geometry codes on plane curves are some of the best with respect to the corresponding parameters. Decoding algorithms for algebraic geometry codes on plane curves have a long history: From syndrome decoding with a strong algebraic geometry component to more down-to-earth error correcting pair and list decoding algorithms. On the other hand, for decoding algorithms that can correct errors beyond half the minimum distance of the given code, \textit{M. Sudan} [J. Complex. 13, No. 1, 180--193 (1997; Zbl 0872.68026)] and \textit{V. Guruswami} and \textit{M. Sudan} [IEEE Trans. Inf. Theory 45, No. 6, 1757--1767 (1999; Zbl 0958.94036)] showed that Reed-Solomon codes and algebraic geometry codes over plane curves can be decoded in polynomial time with an asymptotic radius reaching the Johnson bound, \textit{S. M. Johnson} [IRE Trans. Inform. Theory IT 8 No. 3, 203--207 (1962; Zbl 0102.34602)], and decoding radius exceeding half the minimum distance, with a very limited drawback in practice. The main contribution of the article under review is a new algorithm that correct errors beyond half the minimum distance of the given code and that applies to any code with a power error locating pair. The unified approach of this new algorithm allows its application to Reed-Solomon codes and algebraic geometry codes on plane curves as an abstract reformulation of the power decoding algorithm, and also applies to many cyclic codes, with a correction error beyond the Roos bound, \textit{C. Roos} [IEEE Trans. Inf. Theory 29, 330--332 (1983; Zbl 0519.94010)]. In addition to providing a unified approach for decoding beyond the half minimum distance, an interesting by-product of this new algorithm is the possibility of its applications to cryptanalysis.