Encoding of Algebraic Geometry Codes With Quasi-Linear Complexity O(NlogN)

Fast encoding and decoding of codes have always been an important topic in coding theory as well as complexity theory. Although encoding is easier than decoding in general, designing an encoding algorithm of codes of length <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> with quasi-linear complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>) is not an easy task. Despite of the fact that algebraic geometry codes (AG codes) were discovered in the early 1980s, encoding algorithms of algebraic geometry codes with quasi-linear complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>) have not been found except for the simplest algebraic geometry codes–Reed-Solomon codes. The best-known encoding algorithm of algebraic geometry codes based on a class of plane curves has quasi-linear complexity at least <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N) (Beelen et al. IEEE Trans. Inf. Theory 2021). In this paper, we design an encoding algorithm for algebraic geometry codes with quasi-linear complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>). Moreover, for these fast encodable AG codes, the inverse of encoding, that is, interpolating the message function from the corresponding codeword, can be computed with the same complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>). Our algorithms are applicable to a large class of algebraic geometry codes based on both plane and non-plane curves, including Kummer extensions, Artin-Schreier extensions, and Hermitian field towers.