On the minimum distance of elliptic curve codes

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].