On the discrete logarithm problem in finite fields of fixed characteristic

DOI10.1090/TRAN/7027MaRDI QIDQ4604404zbMATH OpenOpenAlexFDO

Authors Robert Granger, Thorsten Kleinjung, Jens Zumbrägel

Publication date 26 February 2018

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16)

Abstract: For $q$ a prime power, the discrete logarithm problem (DLP) in $mathbb{F}_q$ consists in finding, for any $ginmathbb{F}_q^{imes}$ and $hinlanglegangle$, an integer $x$ such that $g^x=h$. We present an algorithm for computing discrete logarithms with which we prove that for each prime $p$ there exist infinitely many explicit extension fields $mathbb{F}_{p^n}$ in which the DLP can be solved in expected quasi-polynomial time. Furthermore, subject to a conjecture on the existence of irreducible polynomials of a certain form, the algorithm solves the DLP in all extensions $mathbb{F}_{p^n}$ in expected quasi-polynomial time.

Recommendations

• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields
• Computing discrete logarithms
• Indiscreet logarithms in finite fields of small characteristic
• Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity

Cites work

• scientific article; zbMATH DE number 1009704 (Why is no real title available?)
• A general framework for subexponential discrete logarithm algorithms
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Approximate formulas for some functions of prime numbers
• Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in \({\mathbb F}_{2^{4 \cdot 1223}}\) and \({\mathbb F}_{2^{12 \cdot 367}}\))
• Factoring Polynomials Over Large Finite Fields
• Finding Isomorphisms Between Finite Fields
• Generators and irreducible polynomials over finite fields
• On \(x^{q+1}+ax+b\)
• On the discrete logarithm problem in elliptic curves
• On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Solving a $$6120$$ -bit DLP on a Desktop Computer
• Traps to the BGJT-algorithm for discrete logarithms
• \(3\)-designs from PGL\((2,q)\)
• \(X^{2^l+1}+x+a\) and related affine polynomials over \(\mathrm{GF}(2^k\))

Cited in

(39)

• Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
• Computation of a 30750-bit binary field discrete logarithm
• Traps to the BGJT-algorithm for discrete logarithms
• On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
• Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
• The discrete logarithm problem over prime fields: the safe prime case. The smart attack, non-canonical lifts and logarithmic derivatives.
• Discrete logarithm diophantiness
• scientific article; zbMATH DE number 611186 (Why is no real title available?)
• On an probabilistic algorithm solving discrete logarithm problem
• Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
• Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
• On the Complexity of Computing Discrete Logarithms over Algebraic Tori
• Updating key size estimations for pairings
• A new perspective on the powers of two descent for discrete logarithms in finite fields
• Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets
• Cryptography and Coding
• scientific article; zbMATH DE number 1409225 (Why is no real title available?)
• Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation
• A note on cyclic groups, finite fields, and the discrete logarithm problem
• scientific article; zbMATH DE number 5575556 (Why is no real title available?)
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Factor base discrete logarithms in Kummer extensions
• Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation
• Discrete logarithms in \(\mathrm{GF}(p)\)
• Advances in Cryptology – CRYPTO 2004
• Roots of certain polynomials over finite fields
• On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic
• scientific article; zbMATH DE number 7310271 (Why is no real title available?)
• Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
• Computing discrete logarithms
• On the discrete logarithm problem in class groups of curves
• scientific article; zbMATH DE number 2127885 (Why is no real title available?)
• On the discrete logarithm problem
• The discrete logarithm problem from a local duality perspective
• Refined analysis to the extended tower number field sieve
• Indiscreet logarithms in finite fields of small characteristic
• A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• A shorter proof for an explicit formula for discrete logarithms in finite fields

This page was built for publication: On the discrete logarithm problem in finite fields of fixed characteristic

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