## Abstract

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 tilde { mathcal {O}}(text {n}{3/2}) resp. tilde { mathcal {O}}({ittext { 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 tilde { mathcal {O}} 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 tilde { mathcal {O}}(text {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 tilde { mathcal {O}}(text {n}{5/4}) and tilde { mathcal {O}}(text {n}{3/2}) respectively.

Original language | English |
---|---|

Journal | IEEE Transactions on Information Theory |

Volume | 67 |

Issue number | 3 |

Pages (from-to) | 1641-1655 |

ISSN | 0018-9448 |

DOIs | |

Publication status | Published - Mar 2021 |

### Bibliographical note

Funding Information:Manuscript received January 14, 2020; revised August 6, 2020; accepted October 27, 2020. Date of publication December 3, 2020; date of current version February 17, 2021. This work was supported by The Danish Council for Independent Research (DFF-FNU) (the project Correcting on a Curve) under Grant 8021-00030B. (Corresponding author: Grigory Solomatov.) The authors are with the Department of Applied Mathematics and Computer Science, Technical University of Denmark, 2800 Kongens Lyngby, Denmark (e-mail: pabe@dtu.dk; jsrn@dtu.dk; gsol@dtu.dk). Communicated by C. Xing, Associate Editor for Coding Theory. Color versions of one or more figures in this article are available at https://doi.org/10.1109/TIT.2020.3042248. Digital Object Identifier 10.1109/TIT.2020.3042248

Publisher Copyright:

© 1963-2012 IEEE.

## Keywords

- AG code
- Cab code
- Encoding
- Hermitian code
- Norm-trace curve