On the discrete logarithm problem in finite fields of fixed characteristic

DOI10.1090/TRAN/7027zbMATH Open1428.11210arXiv1507.01495OpenAlexW1684267317MaRDI QIDQ4604404FDOQ4604404

Robert Granger, Jens Zumbrägel, Thorsten Kleinjung

Publication date: 26 February 2018

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• On the Function Field Sieve and the Impact of Higher Splitting Probabilities
• 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.)
• Generators and irreducible polynomials over finite fields
• A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
• On \(x^{q+1}+ax+b\)
• Title not available (Why is that?)
• Factoring Polynomials Over Large Finite Fields
• Approximate formulas for some functions of prime numbers
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Breaking ‘128-bit Secure’ Supersingular Binary Curves
• Traps to the BGJT-algorithm for discrete logarithms
• \(X^{2^l+1}+x+a\) and related affine polynomials over \(\mathrm{GF}(2^k\))
• \(3\)-designs from PGL\((2,q)\)
• Finding Isomorphisms Between Finite Fields
• A general framework for subexponential discrete logarithm algorithms
• On the discrete logarithm problem in elliptic curves
• Solving a $$6120$$ -bit DLP on a Desktop Computer

Cited In (30)

• 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
• On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
• Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
• Title not available (Why is that?)
• Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
• On the Complexity of Computing Discrete Logarithms over Algebraic Tori
• Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
• A new perspective on the powers of two descent for discrete logarithms in finite fields
• Updating key size estimations for pairings
• Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets
• Cryptography and Coding
• Title not available (Why is that?)
• Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation
• Title not available (Why is that?)
• A note on cyclic groups, finite fields, and the discrete logarithm problem
• Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation
• Factor base discrete logarithms in Kummer extensions
• Advances in Cryptology – CRYPTO 2004
• Discrete logarithms in \(\mathrm{GF}(p)\)
• 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
• Title not available (Why is that?)
• Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
• Title not available (Why is that?)
• Refined analysis to the extended tower number field sieve
• Indiscreet logarithms in finite fields of small characteristic
• Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
• A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
• 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)