Fast Encoding of AG Codes over C_ab Curves

03/30/2020
by   Peter Beelen, et al.
0

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called C_ab curves, as well as algorithms for inverting the encoding map, which we call "unencoding". Some C_ab curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity Õ(n^3/2) resp. Õ(qn) for AG codes over any C_ab curve satisfying very mild assumptions, where n is the code length and q the base field size, and Õ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, notably the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity Õ(n) for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse–Weil bound, our encoding algorithm has complexity Õ(n^5/4) while unencoding has Õ(n^3/2).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset