Advances in Cryptology – CRYPTO 2004

DOI10.1007/B99099MaRDI QIDQ5311533zbMATH OpenOpenAlexFDO

Authors Qi Cheng

Publication date 23 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0311120

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Decoding (94B35)

Abstract: 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 $$ be the function from integers to the sum of digits in their $q$-ary expansions. We present an algorithm that given $g^e$ ($0leqe<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.32n$. 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)lo{g}^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.

Recommendations

• On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
• On the discrete logarithm problem in finite fields of fixed characteristic
• A note on discrete logarithms in finite fields
• Lower bounds on the linear complexity of the discrete logarithm in finite fields
• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• Cryptography and Coding
• scientific article; zbMATH DE number 2127885
• Computation of discrete logarithms in an arbitrary finite field
• A short proof for explicit formulas for discrete logarithms in finite fields
• Bounds in various generalized settings of the discrete logarithm problem

Cited in

(3)

• On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
• Proving primality in essentially quartic random time
• On the construction of finite field elements of large order

This page was built for publication: Advances in Cryptology – CRYPTO 2004

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311533)