Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Discrete logarithm computations over finite fields using Reed-Solomon codes

Daniel Augot 1, 2 François Morain 2, 1
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : 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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : François Morain <>
Submitted on : Monday, February 20, 2012 - 2:21:56 PM
Last modification on : Thursday, March 5, 2020 - 6:27:24 PM
Long-term archiving on: : Monday, May 21, 2012 - 2:21:56 AM


Files produced by the author(s)


  • HAL Id : hal-00672050, version 1
  • ARXIV : 1202.4361



Daniel Augot, François Morain. Discrete logarithm computations over finite fields using Reed-Solomon codes. 2012. ⟨hal-00672050⟩



Record views


Files downloads