On the Bounded Sum-of-digits Discrete Logarithm Problem in Kummer and Artin-Schreier Extensions

Original · EN

In this paper, we study the discrete logarithm problem in the finite fields ₙ where n|q-1. The field is called a Kummer field or a Kummer extension of. It plays an important role in improving the AKS primality proving algorithm. It is known that we can efficiently construct an element g with order greater than 2ⁿ in the fields. Let Sq() be the function from integers to the sum of digits in their q-ary expansions. We present an algorithm that given gᵉ (0≤ e < qⁿ) finds e in random polynomial time, provided that Sq (e) < n. We then show that the problem is solvable in random polynomial time for most of the exponent e with Sq (e) < 1.32 n. The main tool for the latter result is the Guruswami-Sudan list decoding algorithm. Built on these results, we prove that in the field ⁻¹, the bounded sum-of-digits discrete logarithm with respect to g can be computed in random time O(f(w) ⁴ (qq⁻¹)), 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 extendible to Artin-Schreier extension ₚₚ where p is a prime. Since every finite field has an extension of reasonable degree which is a Kummer field, 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.