On the Bounded Sum-of-digits Discrete Logarithm Problem in Kummer and Artin-Schreier Extensions
| dc.creator | Cheng, Qi | |
| dc.date | 2003-11-07 | |
| dc.date.accessioned | 2026-07-07T05:02:44Z | |
| dc.date.available | 2026-07-07T05:02:44Z | |
| dc.description | In this paper, we study the discrete logarithm problem in the finite fields $\F_{q^n}$ where $n|q-1$. The field is called a Kummer field or a Kummer extension of $\F_q$. 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^n$ in the fields. Let $S_q(\bullet)$ be the function from integers to the sum of digits in their $q$-ary expansions. We present an algorithm that given $g^e$ ($ 0\leq e < q^n $) 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 $. The main tool for the latter result is the Guruswami-Sudan list decoding algorithm. Built on these results, we prove that in the field $\F_{q^{q-1}}$, the bounded sum-of-digits discrete logarithm with respect to $g$ can be computed in random time $O(f(w) \log^4 (q^{q-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 extendible to Artin-Schreier extension $\F_{p^p}$ 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. | |
| dc.description | 10 pages | |
| dc.identifier | https://arxiv.org/abs/math/0311120 | |
| dc.identifier | http://arxiv.org/abs/math/0311120 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69122 | |
| dc.subject | Number Theory | |
| dc.subject | 11Y16 | |
| dc.title | On the Bounded Sum-of-digits Discrete Logarithm Problem in Kummer and Artin-Schreier Extensions | |
| dc.type | text |