On the discrete logarithm problem in finite fields of fixed characteristic

Abstract

For $q$ a prime power, the discrete logarithm problem (DLP) in ${\mathbb{F}}_q$ consists in finding, for any $g\in {\mathbb{F}}_q^{\times }$ and $h\in ⟨g⟩$, 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.

15 pages, 2 figures. To appear in Transactions of the AMS

References in corpus (1)

• Traps to the BGJT-Algorithm for Discrete Logarithms

Cited by in corpus (6)

• Indiscreet logarithms in finite fields of small characteristic
• Lattice Packings of Cross-polytopes from Reed-Solomon Codes and Sidon Sets
• A group law on the projective plane with applications in Public Key Cryptography
• Still Wrong Use of Pairings in Cryptography
• A new perspective on the powers of two descent for discrete logarithms in finite fields
• On the selection of polynomials for the DLP quasi-polynomial time algorithm in small characteristic