Discrete logarithm computations over finite fields using Reed-Solomon codes

Details Discrete logarithm computations over finite fields using Reed-Solomon codes Discrete logarithm computations over finite fields using Reed-Solomon codes

2012-02-20

arxiv.org/abs/1202.4361v1

Mathematics

Number Theory

Scientific paper

Cheng and Wan have related the decoding of Reed-Solomon codes to the computation of discrete logarithms over finite fields, with the aim of proving the hardness of their decoding. In this work, we experiment with solving the discrete logarithm over GF(q^h) using Reed-Solomon decoding. For fixed h and q going to infinity, we introduce an algorithm (RSDL) needing O (h! q^2) operations over GF(q), operating on a q x q matrix with (h+2) q non-zero coefficients. We give faster variants including an incremental version and another one that uses auxiliary finite fields that need not be subfields of GF(q^h); this variant is very practical for moderate values of q and h. We include some numerical results of our first implementations.

Affiliated with

Also associated with

No associations

Rating

Discrete logarithm computations over finite fields using Reed-Solomon codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discrete logarithm computations over finite fields using Reed-Solomon codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete logarithm computations over finite fields using Reed-Solomon codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565298