On the minimum distance of elliptic curve codes
On the minimum distance of elliptic curve codes
复制标题
DOI：
10.1109/isit.2015.7282884
复制
发表时间：
2015-01
期刊：
影响因子：
--
通讯作者：
Jiyou Li;D. Wan;Jun Zhang
中科院分区：
文献类型：
--
作者：
Jiyou Li;D. Wan;Jun Zhang
计算线性码的最小距离是算法编码理论中的基本问题之一。Vardy在文[1]中证明了它对于一般线性码是一个NP-难问题。在实际应用中，人们经常使用具有附加数学结构的码，如循环码和代数几何(AG)码等。本文研究了一族AG码的最小距离。对于亏格为0的AG码(广义Reed-Solomon码)，最小距离有一个简单的显式公式。程[2]的一个有趣的结果是，对于一般的椭圆曲线码(ECAG码或亏格为1的AG码)，最小距离问题已经是NP难的(在RP约简下)。本文证明了当评价集适当大时(至少2=3的群阶)，ECAG码的最小距离也有一个简单的显式公式。我们的方法是纯组合的，基于Li-wan的一种新的筛选技术[3]。
Computing the minimum distance of a linear code is one of the fundamental problems in algorithmic coding theory. Vardy [1] showed that it is an NP-hard problem for general linear codes. In practice, one often uses codes with additional mathematical structure, such as cyclic codes and algebraic geometry (AG) codes, etc. In this paper, we study the minimum distance of a family of AG codes. For AG codes of genus 0 (generalized Reed-Solomon codes), the minimum distance has a simple explicit formula. An interesting result of Cheng [2] says that the minimum distance problem is already NP-hard (under RP-reduction) for general elliptic curve codes (ECAG codes, or AG codes of genus 1). In this paper, we show that the minimum distance of ECAG codes also has a simple explicit formula if the evaluation set is suitably large (at least 2=3 of the group order). Our method is purely combinatorial and based on a new sieving technique from Li-Wan [3].