论文标题
快速编码Ag代码$ C_ {AB} $ curves
Fast Encoding of AG Codes over $C_{ab}$ Curves
论文作者
论文摘要
我们研究了用于在某些平面曲线上编码单点代数几何（Ag）代码的算法，称为$ C_ {AB} $曲线，以及算法以反转编码地图，我们称之为“ Unecroding”。一些$ c_ {ab} $曲线有很多点，甚至最大，例如Hermitian曲线。我们的编码resp。未编码算法具有复杂性$ \ tilde {o}（n^{3/2}）$ resp。 $ \ tilde {o}（qn）$用于任何$ c_ {ab} $曲线满足非常温和的假设，其中$ n $是代码长度，而$ q $ the Base Field大小，而$ \ tilde {o} $忽略了估算中的常数和对数因素。对于曲线的代码，其评估点在类似网格的结构上，尤其是Hermitian曲线和Norm-Trace曲线，我们表明我们的算法具有准线性时间复杂性$ \ tilde {o}（n）$用于这两个操作。对于无限的曲线家族，其点数的数量是远离Hasse的一个不变的因素 - WEEL BOND BOND，我们的编码算法具有复杂性$ \ tilde {o}（n^{5/4}）$，而Unconconding具有$ \ tilde {o} {o}（n^{3/2}）$。
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{O}(n^{3/2})$ resp. $\tilde{O}(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{O}$ 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 $\tilde{O}(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 $\tilde{O}(n^{5/4})$ while unencoding has $\tilde{O}(n^{3/2})$.
