Discrete logarithm computations over finite fields using Reed-Solomon codes
type: Dataset
description: 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.
issued: 2026-05-27T22:34:58.943904
language: en
modified: 2026-05-27T22:34:58.943910
contact point: Organization
  fn: CCSD
keyword: discrete-logarithms-over-finite-fields
keyword: index-calculus-methods
keyword: infoeu-reposemanticspreprint
keyword: infoinfo-ircomputer-science-csinformation-retrieval-csir
keyword: infoinfo-itcomputer-science-csinformation-theory-csit
keyword: mathmath-itmathematics-mathinformation-theory-mathit
keyword: mathmath-ntmathematics-mathnumber-theory-mathnt
keyword: preprints-working-papers-
keyword: reed-solomon-codes
landing page: https://inria.hal.science/hal-00672050

Discrete logarithm computations over finite fields using Reed-Solomon codes
type: Distribution
format: HTML
issued: 2026-05-27T22:34:58.998270
modified: 2026-05-27T22:34:58.911983
access URL: https://inria.hal.science/hal-00672050

test_moissonnage_selune
type: Agent