  Computing the minimum distance of a linear code is one of the fundamental
problems in algorithmic coding theory. Vardy [14] showed that it is an \np-hard
problem for general linear codes. In practice, one often uses codes with
additional mathematical structure, such as 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 [3] 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 the
first two authors [8]. This method also proves a significantly stronger version
of the MDS (maximum distance separable) conjecture for ECAG codes.
