We give a method to construct deep holes for elliptic curve codes. For long elliptic curve codes, we conjecture that our construction is complete in the sense that it gives all deep holes. Some evidence and heuristics on the completeness are provided by means of connections with problems and results in finite geometry.

Let Fq be the finite field of q elements. In this paper we obtain bounds on the following counting problem: given a polynomial f (x) ∈ Fq[x] of degree k + m and a non-negative integer r, count the number of polynomials g(x) ∈ Fq[x] of degree at most k - 1 such that f (x) + g(x) has exactly r roots in Fq. Previously, explicit formulas were known only for the cases m = 0, 1, 2. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code [q, k, q - k + 1]q.

Projective Reed-Solomon (PRS) codes are Reed-Solomon codes of the maximum possible length q+1. The classification of deep holes-received words with maximum possible error distance- for PRS codes is an important and difficult problem. In this paper, we use algebraic methods to explicitly construct three classes of deep holes for PRS codes. We show that these three classes completely classify all deep holes of PRS codes with redundancy four. Previously, the deep hole classification was only known for PRS codes with redundancy at most three.

In this paper, we obtain new results on the covering radius and deep holes for projective Reed-Solomon (PRS) 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].

Stopping sets and stopping set distribution of a linear code play an important role in the performance analysis of iterative decoding for this linear code. Let C be an [n, k] linear code over Fqwith parity-check matrix H, where the rows of H may be dependent. Let [n] = {1, 2,...,n} denote the set of column indices of H. A stopping set S of C with parity-check matrix H is a subset of [n] such that the restriction of H to S does not contain a row of weight 1. The stopping set distribution {Ti(H)}i=0nenumerates the number of stopping sets with size i of C with parity-check matrix H. Denote H*, the parity-check matrix, consisting of all the nonzero codewords in the dual code C⊥. In this paper, we study stopping sets and stopping set distributions of some residue algebraic geometry (AG) codes with parity-check matrix H*. First, we give two descriptions of stopping sets of residue AG codes. For the simplest AG codes, i.e., the generalized Reed-Solomon codes, it is easy to determine all the stopping sets. Then, we consider the AG codes from elliptic curves. We use the group structure of rational points of elliptic curves to present a complete characterization of stopping sets. Then, the stopping sets, the stopping set distribution, and the stopping distance of the AG code from an elliptic curve are reduced to the search, counting, and decision versions of the subset sum problem in the group of rational points of the elliptic curve, respectively. Finally, for some special cases, we determine the stopping set distributions of the AG codes from elliptic curves.

Every finite field has many multiplicative generators. However, finding one in polynomial time is an important open problem. In fact, even finding elements of high order has not been solved satisfactorily. In this paper, we present an algorithm that for any positive integer c and prime power q, finding an element of order in the finite field in deterministic time (qc)O(1). We also show that there are many weak keys for the discrete logarithm problems in those fields with respect to certain bases.

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log1-ϵnunlessNP⊆RTIME(2polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unlessP=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log1-ϵnunlessNP⊆DTIME(2polylog(n)). As the main technical contribution, for any constant 2/3s, runs in timepoly(s) and constructs a codeCof lengthpoly(s) with an explicit Hamming ball of radius ρd(C), such that the projection at the firstscoordinates sends the codewords in the ball surjectively onto a linear subspace of dimensions, whered(C) denotes the minimum distance ofC. The codes are obtained by concatenating Reed-Solomon codes with Hadamard codes.

It has been proved that the maximum likelihood decoding problem of Reed-Solomon codes is NP-hard. However, the length of the code in the proof is at most polylogarithmic in the size of the alphabet. For the complexity of maximum likelihood decoding of the primitive Reed-Solomon code, whose length is one less than the size of alphabet, the only known result states that it is at least as hard as the discrete logarithm in some cases where the information rate unfortunately goes to zero. In this paper, it is proved under a well known cryptography hardness assumption that: 1) There does not exist a randomized polynomial time maximum likelihood decoder for the Reed-Solomon code family [q, k(q)]q, where k(x) is any function in Z+→ Z+computable in time xO(1)satisfying √x ≤ k(x) ≤ x - √x. 2) There does not exist a randomized polynomial time bounded-distance decoder for primitive Reed-Solomon codes at distance 2/3 + ϵ of the minimum distance for any constant 0 <; ϵ <; 1/3. In particular, this rules out the possibility of a polynomial time algorithm for maximum likelihood decoding problem of primitive Reed-Solomon codes of any rate under the assumption.

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete in [14]. In [8], the gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log1-e n unless NP ⊆ RTIME(2polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log1-en unless NP ⊆ DTIME(2polylog(n)). As the main technical contribution, for any constant 2/3

For an error‐correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed–Solomon code $[n,k]_q$, a simple counting argument shows that for any integer $0 0 $. We show that the discrete logarithm problem over ${\bf F}_{q^{h}}$ can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed–Solomon code $[q, g-h]_q$ with radius $q - g$. These results show that the decoding problems for the Reed–Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding problem of Reed–Solomon codes, although the infeasible radius that we obtain is much larger than the radius, which is known to be feasible, it is the first nontrivial bound. Our result on the bounded distance decodability of Reed–Solomon codes is also the first of its kind. The main tools for obtaining these results are an interesting connection between the problem of list decoding of Reed–Solomon code, the problem of a discrete logarithm over finite fields, and a generalization of Katz’s theorem on representations of elements in an extension finite field by products of distinct linear factors.

For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k]/sup q/, a simple counting argument shows that for any integer 00. We show that the discrete logarithm problem over F/sub qh/ can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g - h]/sub q/ with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over finite fields. The main tools to obtain these results are an interesting connection between the problem of list-decoding of Reed-Solomon code and the problem of discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors.