2004 | OriginalPaper | Buchkapitel
On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
verfasst von : Qi Cheng
Erschienen in: Advances in Cryptology – CRYPTO 2004
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study the bounded sum-of-digits discrete logarithm problem in finite fields. Our results concern primarily with fields ${\mathbf F}_{q^n}$ where n|q–1. The fields are called Kummer extensions of F q . It is known that we can efficiently construct an element g with order greater than 2n in the fields. Let S q ( ∙ ) be the function from integers to the sum of digits in their q-ary expansions. We first present an algorithm that given ge ( 0≤ e < qn ) finds e in random polynomial time, provided that S q (e) < n. We then show that the problem is solvable in random polynomial time for most of the exponent e with S q (e) < 1.32 n , by exploring an interesting connection between the discrete logarithm problem and the problem of list decoding of Reed-Solomon codes, and applying the Guruswami-Sudan algorithm. As a side result, we obtain a sharper lower bound on the number of congruent polynomials generated by linear factors than the one based on Stothers-Mason ABC-theorem. We also prove that in the field ${\mathbf F}_{q^{q-1}}$, the bounded sum-of-digits discrete logarithm with respect to g can be computed in random time O(f(w) log4 (qq − − 1)), where f is a subexponential function and w is the bound on the q-ary sum-of-digits of the exponent, hence the problem is fixed parameter tractable. These results are shown to be generalized to Artin-Schreier extension ${\mathbf F}_{p^p}$ where p is a prime. Since every finite field has an extension of reasonable degree which is a Kummer extension, our result reveals an unexpected property of the discrete logarithm problem, namely, the bounded sum-of-digits discrete logarithm problem in any given finite field becomes polynomial time solvable in certain low degree extensions.