Previously Published Works UC Irvine

1 Previously Published Works UC Irvine A University of California author or department has made this article openly available. Thanks to the Academic ...

Author:  Bryan Bridges
0 downloads 0 Views 223KB Size

Previously Published Works UC Irvine A University of California author or department has made this article openly available. Thanks to the Academic Senate’s Open Access Policy, a great many UC-authored scholarly publications will now be freely available on this site. Let us know how this access is important for you. We want to hear your story! http://escholarship.org/reader_feedback.html

Peer Reviewed Title: ON the list and bounded distance decodability of Reed-Solomon codes Journal Issue: SIAM Journal on Computing, 37(1) Author: Cheng, Q Wan, D Publication Date: 12-01-2007 Series: UC Irvine Previously Published Works Permalink: http://escholarship.org/uc/item/8wc6425s DOI: https://doi.org/10.1137/S0097539705447335 Local Identifier(s): UCPMS ID: 122693 Abstract: 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 < g < n, there exists at least one Hamming ball of radius n - g, which contains at least ( g n )/q g-k many codewords. Let ĝ(n, k, q) be the smallest positive integer g such that ( g n )/q g-k ≤ 1. One knows that k - 1 ≤ ĝ(n, k, q) ≤ √n(k - 1) ≤ n. For the distance bound up to n - √n(k - 1), it is known that both the list and bounded distance decoding can be solved efficiently. For the distance bound between n - √n(k - 1) and n-ĝ(n, k, q), we do not know whether

eScholarship provides open access, scholarly publishing services to the University of California and delivers a dynamic research platform to scholars worldwide.

the Reed-Solomon code is list or bounded distance decodable; nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: (1) List decoding cannot be done for radius n - ĝ(n, k, q) or larger, unless the discrete logarithm over F qĝ(n, k, q)-k is easy. (2) Let h and g be positive integers satisfying q ≥ max(g 2 , (h - 1) 2+ε ) and g ≥ (4/ε + 2)(h +1) for a constant ε > 0. We show that the discrete logarithm problem over F qh 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. © 2007 Society for Industrial and Applied Mathematics. Copyright Information: All rights reserved unless otherwise indicated. Contact the author or original publisher for any necessary permissions. eScholarship is not the copyright owner for deposited works. Learn more at http://www.escholarship.org/help_copyright.html#reuse

eScholarship provides open access, scholarly publishing services to the University of California and delivers a dynamic research platform to scholars worldwide.

arXiv:math/0405082v1 [math.NT] 5 May 2004

On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract) Qi Cheng∗

Daqing Wan†

Abstract For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within the given distance to a received message. The bounded distance decoding problem, on the other hand, is to find one codeword if there exists one or more codewords within the given distance, or to output the empty set if there does 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 g < n, (ng) many there exists at least one Hamming ball of radius n − g, which contains at least qg−k n (g) < 1. For the distance codewords. Let gˆ(n, k, q) be the smallest integer g such that qg−k √ bound between n − nk and n − gˆ(n, k, q), we do not know whether the Reed-Solomon code is list, or bounded distance decodable, nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answers to both questions are no. There are public key cryptosystems proposed recently, whose security is based on the assumptions. In this paper, we prove: (1) List decoding can not be done for radius n − gˆ(n, k, q) or larger, otherwise the discrete logarithm over Fqgˆ(n,k,q)−k is easy. (2) Let h be a positive integer satisfying h < q 1/4 − 2. We show that the discrete logarithm problem over Fqh can be efficiently reduced to the bounded distance decoding problem of the Reed-Solomon code [q, 3h + 4]q with radius q − 4h − 4. 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 problems of list-decoding of Reed-Solomon code and the problems of discrete logarithms over finite fields, and a generalization of the Katz’s theorem, which concerns representations of elements in an extension finite field by products of linear factors.

1

Introduction and Motivation

An error-correcting code C over an alphabet Σ is an injective map φ : Σk → Σn . When we need to transmit a message of k letters over a noisy channel, we apply the map on the message first ( ∗

School of Computer Science, the University of Oklahoma, Norman, OK 73019, USA. Email: [email protected] This research is partially supported by NSF Career Award CCR-0237845. † Department of Mathematics, University of California, Irvine, CA 92697. Email: [email protected] Institute of Mathematics, Chinese Academy of Sciences, Beijing, P.R. China. Partially supported by NSF and NSFC.

1

i.e. encode the message ) and send its image (i.e. the codeword) of n letters over the channel. The Hamming distance between two sequence of letters of the same length is the number of positions where two sequences differ. A good error-correcting code should have a large minimum distance d, which is defined to be the minimum Hamming distance between any two codewords in φ(Σk ). A received message, possibly corrupted, but with no more than (d − 1)/2 errors, corresponds to a unique codeword, thus may be decoded into the original message despite errors occur during the communication. Error-correcting codes are widely used in practice and are mathematically interesting and intriguing. It attracts the attention of theoretical computer science community recently. Several major achievements of theoretical computer science, notably the Probabilistically Checkable Proofs and derandomization techniques, rely heavily on the techniques in error-correcting codes. We refer to the survey [14] for details. For the purpose of efficient encoding and decoding, Σ is usually set to be a finite field, and the map φ is set to be linear. Numerous error correcting codes have been proposed, among them, the Reed-Solomon codes are particularly important. They were deployed to transmit information from and to spaceships, and were used to store information in optical media. The Reed-Solomon code [n, k]q , is the map from a0 , a1 , · · · , ak−1 ∈ Fq to (a0 + a1 x + · · · + ak−1 xk−1 )x∈S⊆Fq for some |S| = n. (The choice of S will not affect our results in this paper. ) Since any two different polynomials with degree k − 1 can share at most k − 1 points, the minimum distance of the Reed-Solomon code is n − k + 1. If the radius of a Hamming ball is less than half of the minimum distance, there should be at most one codeword in the Hamming ball. Finding the codeword is called unambiguous decoding. It was solved, see [2] for a simple algorithm. If we gradually increase the radius, there will be two or more codewords lying in some Hamming balls. Can we efficiently enumerate all the codewords in any Hamming ball of certain radius? This is the so called list decoding problem. The notion was first introduced by Elias [5]. There was virtually no progress on this problem for radius slightly larger than half of the minimum distance, until Sudan published his influential paper [13]. His result was subsequently improved, the best √ algorithm [9] solves the list decoding problem for radius as large as n − nk. The work sheds new light on the limitation of list decodibility of Reed-Solomon codes. To the other extreme, if the radius is greater than or equal to the minimum distance, there are exponentially many codewords in some Hamming balls. The decoding problem of Reed-Solomon codes can be formulated into the problem of curve fitting or polynomial reconstruction. In the problem, we are given n points (x1 , y1 ), (x2 , y2 ), · · · , (xn , yn ). The goal is to find polynomials of degree k − 1 that pass at least g points. In this paper, we only consider the case when points have distinct x-coordinates. If we allow multiple occurrences of x-coordinates, the problem is NP-hard [6], and it is not relevant to the Reed-Solomon decoding problem. √ If g ≥ (n + k)/2, it corresponds √ to the unambiguous decoding of Reed-Solomon codes. If g > nk, the radius is less than n − nk, the problem can be solved by the Guruswami-Sudan algorithm. If g ≤ k, it is possible that there are exponentially many solutions, but finding one is very easy. In this paper, we study the following question: How large can we increase the radius before the list decoding problem or the bounded distance decoding problem become infeasible? The question has been under intensive investigations for Reed-Solomon codes and other error-correcting codes. The case of general non-linear codes has been solved [6]. The case for linear codes is much harder.

2

Some partial results have been obtained in [8, 7]. However, none of them applies to Reed-Solomon codes. No negative result is known about the list decodibility of Reed-Solomon codes, except a simple bound given by Justesen and Hoholdt [10], which states that for any positive integer g < n, n g−k there exists at least one Hamming ball of radius n − g, which contains at least g /q many codewords. This bound matches the intuition well, consider an imaginary algorithm as follows: randomly select g points from the n input points, and use polynomial interpolation to get a polynomial of degree at most g − 1 which passes these g points. Then with probability 1/q g−k , the result polynomial has degree k − 1. The sample space has size ng . Thus heuristically, the  number of codewords in Hamming balls of radius n − g is at least ng /q g−k on the average. In the same paper, Justesen and Hoholdt also gave an upper bound for the radius of the Hamming balls containing a constant or less number of codewords.  If we gradually increase g, starting from k, then ng /q g−k will fall below 1 at some point. √ However, g is still very far away from nk. Let gˆ(n, k, q) be the smallest integer such that  g−k n /q is less than 1. The following lemma shows that there is a gap between gˆ(n, k, q) and √g nk. √  Lemma 1 1. For positive integers k < g < n, if g > nk, then ng−k > ng (which implies  that q g−k > ng ).  2. For any constant 0 < c1 < 1/2 and fixed k/n, if g = k + c1 (n − k), then ng /ng−k ≤ 2−c2 n for some positive constant c2 . In fact, for a fixed rate (k/n) and q = Θ(n), gˆ(n, k, q) = k + Θ( logn n ). We prove that if the list decoding of the [n, k]q Reed-Solomon code is feasible when radius is n− gˆ(n, k, q), then the discrete logarithm over Fqgˆ(n,k,q)−k is easy. In the other words, we prove that the list decoding is not feasible for radius n − gˆ(n, k, q) or larger, assuming that the discrete logarithm over Fqgˆ(n,k,q)−k is hard. Note that it does not rule out the possibility that there are only polynomially many codewords in all Hamming balls of radius n − gˆ(n, k, q), even assuming that intractability of the discrete logarithm over Fqgˆ(n,k,q)−k . Theorem 1 If there exists an algorithm solving the list decoding problem of radius n − gˆ(n, k, q) for the Reed-Solomon code [n, k]q in time q O(1) , then discrete logarithm over finite field Fqgˆ(n,k,q)−k can be computed in time q O(1) . When the list decoding problem is hard for certain radius, or a Hamming ball contains too many codewords for us to enumerate all of them, we can turn our attention to designing an efficient bounded distance decoding algorithm, which only need to output one of codewords in the ball, or output the empty set in case that the ball does not contain any codeword. However, we prove that the bounded distance decoding is hard as well. Theorem 2 Let q be a prime power and h be a positive integer satisfying q > (h + 2)4 . If the bounded distance decoding problem of radius q − 4h − 4 for the Reed-Solomon code [q, 3h + 4]q can be solved in time q O(1) , the discrete logarithm problem over Fqh can be solved in time q O(1) .

3

To prove the theorem, we naturally come across the following question: In a finite field Fqh , for any α such that Fqh = Fq [α], can Fq + α generate the multiplicative group (Fqh )∗ ? This interesting problem has a lot of applications in graph theory, and it has been studied by several number theorists. Chung [4] proved that if q > (h − 1)2 , then (Fqh )∗ is generated by Fq + α. Wan [16] showed a negative result that if q h − 1 has a divisor d > 1 and h ≥ 2(q logq d + logq (q + 1)), then (Fqh )∗ is not generated by Fq + α for some α. Katz [11] applied the Lang-Weil method, and showed that for every h ≥ 2 there exists a constant B(h) such that for any finite field Fq with q ≥ B(h), any element in (Fqh )∗ can be written as a product of exactly n = h + 2 distinct elements from Fq + α. Clearly B(h) has to be an exponential function. In this paper, we obtain a generalization of the Katz’s theorem, in which we use a bigger n and manage to decrease B(h) to a polynomial function. For details, see Section 3.2 It is generally believed that the list decoding problem and the bounded distance decoding for √ Reed-Solomon codes are computationally hard if the number of errors is greater than n− nk and less than n − k. This problem is even used as a hard problem to build public key cryptosystems and pseudorandom generators [12]. A similar problem, noisy polynomial interpolation [3], was proved to be vulnerable to the attack of lattice reduction techniques, hence is easier than originally thought. This raises concerns on the hardness of polynomial reconstruction problem. Our results confirm the belief that polynomial reconstruction problem is hard, under a well-studied hardness assumption in number theory, hence provide a firm foundation for many protocols based on the problem. This paper is organized as follows. In Section 2, we prove Lemma 1. In Section 3, we sketch the proof of Theorem 1 and Theorem 2. In Section 4, we show an interesting duality between the size of a group generated by linear factors, and the list size in Hamming balls of Reed-Solomon codes.

2

Proof of Lemma 1

In this section, we prove Lemma 1 by showing the following statement. Theorem 3 There is no positive integral solution for   n > nh g p n(g − h). g >

(1) (2)

We first obtain a finite range for h, g and n. Lemma 2 If (n, g, h) is a positive integral solution, then h < 88. p p Proof: Denote g/h by α and n/h by β. From g > n(g − h), we have α > β(α − 1). Hence 1 . α < β < α + 1 + α−1 √ √ 1 ). Recall that for any positive integer i, 2πi(i/e)i ≤ i! ≤ 2πi(i/e)i (1 + 12i−1   β β n βh h g = αh ≤ ( αα (β−α)β−α ) . Thus

ββ αα (β−α)β−α

≥ βh, which implies

4

h≤ Recall some facts:

β β−1 . αα (β − α)β−α

1. For x > 0, xx takes the minimum value 0.6922.. at x = e−1 = 0.36787944.... 2. For x > 0, 1 ≤ (1 + x1 )x ≤ e = 2.7182818284... If α ≥ 2, then β − α ≤ 1 + h ≤

1 α−1

≤ 2. We have

1.45β β−1 αα

(α+

If α < 2, h ≤ If β > 3, then

1

)

1 α−1 1.45(1 + α + α−1 ) ≤ αα 1 1 1 1 ( α−1 ) (1 + + ) )α ≤ 1.45(1 + α + α−1 α α(α − 1) ≤ 1.45 ∗ 4 ∗ e ∗ 2 < 32.

1.45β β−1 . (β−α)β−α

There are two cases. If β ≤ 3, then h ≤ 1.452 ∗ 9 < 19.

β β−1 ) (β − α)α−1 β −α β β−1 1 α−1 ≤ 1.45( ) (1 + ) β −2 α−1 ≤ 1.45 ∗ e3 ∗ 3 < 88.

h ≤ 1.45(

2 Corollary 1 α ≥ 88/87 and β − α < 88. Note that if α < 89, then β < 178. If α ≥ 89, then β − α ≤ 1 + 1/88, but n − g = (β − α)h is an integer, and h ≤ 87, so β − α ≤ 1. So if n > 2h, (1) can not hold. Proof: Now we can finish proving the main theorem of this section, by exhaustively searching for the solutions in the finite range that h < 88, n < 178 ∗ 88 = 15664 and h < g < n in a computer. 2 Similarly we can show that for any constant c, the inequalities   n ≥ nh−c g p t(g − h) g >

(3) (4)

have only finite many positive integral solutions. g n by γ and g−k by δ. To prove the second part of the lemma, it suffices to see that Denote g−k g−k γ(g−k) n for some constant c2 only depending on α and β. g = δ(g−k) ≤ c2 5

3

The Decoding Problem of Reed-Solomon Codes and the Discrete Logarithm over Finite Fields

Let q be a prime power and let Fq be the finite field with q elements. Let S be a subset of Fq of n elements. For a positive integer g ≤ n, consider Sg = {A|A ⊆ S, |A| = g}. Q

For any A ∈ Sg , denote a∈A (x − a) by PA (x). Let h(x) be an irreducible monic polynomial over Fq of degree h < g. Define a map ψ : Sg → Fq [x]/(h(x)) by ψ(A) = PA (x)

(mod h(x)).

For any f (x) in Fq [x]/(h(x)), if ψ −1 (f (x)) is not empty, then there exists at least one polynomial t(x) and one A ∈ Sn such that f (x) + t(x)h(x) = PA (x). For any a ∈ A, PA (a) = 0, t(a) = −f (a)/h(a). Hence there are at least g elements in S which are the roots of f (x) + t(x)h(x) = 0, and the curve y = t(x) passes at least g points in the following set of n points: {(a, −f (a)/h(a))|a ∈ S}. According to Pigeonhole principle, there must exist a polynomial fˆ(x) such that |ψ −1 (fˆ(x))| ≥ (n) |Sg |/|Fq [x]/(h(x))| = qgh . Note that t(x) has degree g − h and leading coefficient 1. For any polynomial f ∈ Fq [x] of degree at most h−1, let Tf (x) be the set of polynomial t(x) of degree g −h such that f (x) + t(x)h(x) = PA (x) for some A ∈ Sg , and let Cf (x) be the set of codewords within distance of n − g to the received word (−f (a)/h(a) − ag−h )a∈S in Reed-Solomon code [n, g − h]q . There is a one-to-one correspondence between Tf (x) and Cf (x) , by sending any t(x) ∈ Tf (x) to (t(a) − ag−h )a∈S . Suppose that we know f (x) and h(x), but not A, are we still able to find t(x)? This is just a list decoding problem of Reed-Soloman code [n, g − h]q . Once we have a list of t(x), we can find A by factoring f (x) + t(x)h(x). This provides a general framework for the following proofs.

3.1

The proof of Theorem 1

Given a Reed-Solomon  code [n, k]q , let h = gˆ(n, k, q) − k. Recall that gˆ(n, k, q) is the smallest integer such that ng /q g−k is less than 1, and h is the degree of an irreducible polynomial h(x). We show that there is an efficient algorithm to solve the discrete logarithm over Fqgˆ(n,k,q)−k = Fq [x]/(h(x)) if there is efficient list decoding algorithm for the Reed-Solomon code [n, k]q with radius n − gˆ(n, k, q). Let α = x (mod h(x)). Suppose that we are given the base b(α) and we need to find out the discrete logarithm of t(α) with respect to the base, where b and t are polynomials over Fq of degree at most h − 1. That there is an efficient list decoding algorithm implies: 1. There are only polynomially many codewords in any Hamming ball of radius n − gˆ(n, k, q), which in turn implies that |ψ −1 (f )| ≤ q c for any f ∈ Fqh and a constant c. Hence  n |ψ(Sgˆ(n,k,q) )| ≥

gˆ(n,k,q) qc

= Θ(q gˆ(n,k,q)−k /q c ) = Θ(q h /q c ).

6

2. And they can be found in polynomial time. We use the index calculus algorithm with factor bases (α + a)a∈S . If we randomly select an integer i between 0 and q gˆ(n,k,q)−k − 1, then with probability bigger than 1/q c , ψ −1 (b(α)i ) is not empty. Apply the list decoding algorithm, we get relations Y Y (α + a) (α + a) = · · · = b(α)i = f (α) = a∈Al

a∈A1

for some A1 , A2 , · · · , Al ∈ Sgˆ(n,k,q) where l is the list size. From the relations, we get linear equations. i=

X

a∈A1

logb (α + a) = · · · =

X

(mod q gˆ(n,k,q)−k − 1)

logb (α + a)

a∈Al

We repeat the above procedure. Since i is picked randomly, and Sg is the sample space, the probability that the new equation is linear independent to the previous ones is very high at the beginning of the algorithm. It would not take long time before we get n independent equations. Solving the system of equations gives us logb (α + a) for all a ∈ Fq . In the last step, for a random i, we compute b(α)i t(α). If ψ −1 (b(α)i t(α)) is not empty, we can solve logb t immediately. This proves the main theorem.

3.2

The proof of Theorem 2

Theorem 4 Let q be a prime power and let h be a positive integer. If q ≥ (h + 2)4 , then every element in F∗qh can be written as a product of exactly 4h + 4 distinct factors from {α + a|a ∈ Fq }, for any α such that Fq (α) = Fqh . Proof: We thank Chaohua Jia for helpful discussion on the proof of this theorem. Fix an α such that Fq (α) = Fqh . For β ∈ F∗qh , let Nk (β) denote the number of solutions of the equation k Y (α + ai ), ai ∈ Fq , β= i=1

where the ai ’s are distinct. We need to show that for k = 4h + 4, the number Nk (β) is always positive if q ≥ (h + 2)4 . Let G be the character group of the multiplicative group F∗qh , which is a cyclic group of order q h − 1. A simple inclusion-exclusion argument shows that 1 Nk (β) ≥ h ( q −1

X

ai ∈Fq ,1≤i≤k



X

X

)

X

1≤i1
For non-trivial χ, one has the well-known Weil estimate X √ | χ(α + a)| ≤ (h − 1) q. a∈Fq 7

χ

−1

k Y (β)χ( (α + ai )). i=1

We deduce that

   q k − k2 q k−1 k Nk (β) ≥ − (1 + )(h − 1)k q k/2 . 2 qh − 1

In order for Nk (β) > 0, it suffices to have the inequality     k k k/2−1−h (q − )q > (1 + (h − 1)k . 2 2

 This inequality is clearly satisfied if both q > 2 k2 + 1 = k(k − 1) + 1 and q k/2−1−h > (h − 1)k . These two inequalities are satisfied if we take k = 4h + 4 and q ≥ (h + 2)4 . The theorem is proved. 2 Now we are ready to prove Theorem 2 Proof: Let h(x) be an irreducible polynomial over Fq of degree h. Then Fqh = Fq [x]/(h(x)). Denote x (mod h(x)) as α. Suppose we need to solve the discrete logarithm of t(α) base b(α) in Fqh , where b and t are polynomials of degree at most h − 1. We let S = Fq . (Fq )4h+4 = {A|A ⊆ Fq , |A| = 4h + 4}. First we randomly select an integers i between 0 and q h −1. Compute b(α)i , and let f (α) be the result where f (x) is a polynomial of degree at most h−1. Now run the bounded distance decoding algorithm on the Reed-Solomon code [q, 3h + 4]q with the point set {(a, −f (a)/h(a) − a3h+4 )|a ∈ Fq } and the distance bound q − 4h − 4. Then according to Theorem 4, the answer is not the empty set. Let the answer be t(x) − x3h+4 . The polynomial t(x) has degree 3h + 4, and agrees with {(x, −f (x)/h(x))|x ∈ Fq } at 4h + 4 many points or more. The polynomial f (x) + t(x)h(x) has degree at most 4h + 4, but has at least 4h + 4 many distinct Q zeros, thus it will be completely splitted as a product of linear factors. Let f (x) + t(x)h(x) = a∈A (x + a) for some A ∈ (Fq )4h+4 . Write it in another way, Y bi = (α + a). a∈A

We get i=

X

a∈A

logg (α + a) (mod q h − 1).

However, we may not be able to solve logg (α + a) for all a ∈ Fq , since the latter relations may be linearly dependent on the former relations. This is the case, for instance, when all the Ai ’s come from a subset of Fq . After we detect that, we start to compute t(α)b(α)x , and find its representation of product of linear factors. Any linear dependence will give us the discrete logarithm of t(α) base b(α). 2

4

Group Size and List Size

Let q be a prime power, and S be a subset of Fq of n elements, where n is very small compared to q. Let α be an element in Fqh such that Fq [α] = Fqh . What is the order of the subgroup 8

generated by α + S for some S ⊆ Fq ? This question has an important application in analyzing the performance of the AKS primality testing algorithm [1]. Experimental data suggests that the order is greater than q h/c for some absolute constant c for |S| ≥ h log q. If we can prove it, the space complexity of the AKS algorithm can be cut by a factor of log p (p is the input prime whose primality certificate is sought), which will make (the random variants of ) the algorithm comparable to the primality proving algorithm used in practice. However, the best known lower bound is (c|S|/h)h for some absolute constant c [15]. We discover an interesting duality between the group size and the list size in Hamming balls of certain radius. Theorem 5 Let k, n be positive integers and q be a prime power. One of the following statements must be true. 1. For any constant c1 , there exists a Reed-Solomon code [n, k]q (n/3 < k < n/2), and a Hamming ball of radius n − gˆ(n, k, q) containing more than c1 1.9n codewords. 2. Let s = log q, the group generated by α + S, has cardinality at least q h/c2 for some absolute constant c2 , where S ⊆ Fq and |S| = s log q. To prove the first statement would solve an important open problem in the Reed-Solomon codes. To prove the second statement would give us a primality proving algorithm much more efficient in term of space complexity than the original AKS and its random variants, hence make the AKS algorithm not only theoretical interesting, but also practical important. However, at this stage we cannot figure out which one is true. What we can prove, however, is that one of them must be true. Note that it is also possible that both of the statements are true. Proof: Let s = log q, k = sh/2 − h and n = sh. So the rate k/n is very close to 1/2 as s gets large, and gˆ(n, k, q) = sh/2. Assume the first statement is wrong, this means that there exists a constant c3 such that for any Reed-Solomon code [n, k]q with n/3 < k < n/2, the number of codewords in any Hamming ball of radius n − gˆ(n, k, q) is less than c3 1.9n . The number of balls containing at least one codeword with that radius and center point at (−f (a)/h(a) − ak )a∈S∈Fq , where f ∈ Fq [x] has degree less than h is greater than q h /(c3 1.9n ) = q h−n log 1.9/ log q /c3 ≥ q h/c , which is a low bounded of the size of the group generated by α + S.

5

2

Concluding Remarks

Interesting open questions include whether the decoding problem of Reed-Solomon code is equivalent to or harder than the discrete logarithm over finite fields, and whether there exists a polynomial time quantum algorithm to solve the decoding problem of Reed-Solomon code.

References [1] M. Agrawal, N. Kayal, and N. Saxena. http://www.cse.iitk.ac.in/news/primality.pdf, 2002. 9

Primes

is

in

P.

[2] E. Berlekamp and L. Welch. Error correction of algebraic block codes. U.S. Patent Number 4633470, 1986. [3] Daniel Bleichenbacher and Phong Q. Nguyen. Noisy polynomial interpolation and noisy chinese remaindering. In Proceedings of EuroCrypto, volume 1807 of Lecture Notes in Computer Science, 2000. [4] F.R.K. Chung. Diameters and eigenvalues. Journal of American Mathematical Society, 2(2):187–196, 1989. [5] Peter Elias. List decoding for noisy channels. In 1957-IRE WESCON Convention Record, pages 94–104, 1957. [6] O. Goldreich, R. Rubinfeld, and M. Sudan. Learning polynomials with queries: the highly noisy case. SIAM Journal on Discrete Mathematics, 2000. [7] V. Guruswami. Limits to list decodability of linear codes. In Proc. 34th ACM Symp. on Theory of Computing, 2002. [8] V. Guruswami, J. Hastad, M. Sudan, and D. Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021–1034, 2002. [9] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory, 45(6):1757–1767, 1999. [10] Jorn Justesen and Tom Hoholdt. Bounds on list decoding of mds codes. IEEE Transactions on Information Theory, 47(4):1604–1609, 2001. [11] Nicholas M. Katz. Factoring polynomials in finite fields: an application of Lang-Weil to a problem in graph theory. Mathematische Annalen, 286:625–637, 1990. [12] Aggelos Kiayias and Moti Yung. Cryptographic hardness based on the decoding of ReedSolomon codes. In Proceedings of ICALP, volume 2380 of Lecture Notes in Computer Science, 2002. [13] Madhu Sudan. Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180–193, 1997. [14] Madhu Sudan. Coding theory: Tutorial & survey. In Proc. 42th IEEE Symp. on Foundations of Comp. Science, pages 36–53, 2001. [15] J. F. Voloch. On some subgroups of the multiplicative group of finite rings. http://www.ma.utexas.edu/users/voloch/preprint.html, 2003. [16] Daqing Wan. Generators and irreducible polynomials over finite fields. Mathematics of Computation, 66(219):1195–1212, 1997.

10

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 DOKUMENTIS.COM - All rights reserved.