Name
Abstract | ||
|---|---|---|
AbstractWe 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}}({\it\text { 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/TIT.2020.3042248 | Periodicals |
Keywords | DocType | Volume |
Encoding, AG code, Hermitian code, C-ab code, norm-trace curve | Journal | 67 |
Issue | ISSN | Citations |
3 | 0018-9448 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Beelen | 1 | 116 | 15.95 |
| Johan Rosenkilde | 2 | 1 | 2.38 |
| Grigory Solomatov | 3 | 1 | 0.35 |