Fast Encoding of AG Codes Over Cab Curves

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called Cab curves, as well as algorithms for inverting the encoding map, which we call “unencoding”. Some Cab 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, for example 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 and unencoding algorithms have complexities Õ(n
^5/4
) and Õ(n
^3/2
) respectively.