On the discrete logarithm problem in finite fields of fixed characteristic
From MaRDI portal
Abstract: For a prime power, the discrete logarithm problem (DLP) in consists in finding, for any and , an integer such that . We present an algorithm for computing discrete logarithms with which we prove that for each prime there exist infinitely many explicit extension fields 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 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
- 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
- scientific article; zbMATH DE number 1009704 (Why is no real title available?)
- 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
(43)- Discrete logarithms in \(\mathrm{GF}(p)\)
- A note on cyclic groups, finite fields, and the discrete logarithm problem
- Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
- Factor base discrete logarithms in Kummer extensions
- Indiscreet logarithms in finite fields of small characteristic
- Updating key size estimations for pairings
- Refined analysis to the extended tower number field sieve
- On the discrete logarithm problem
- The discrete logarithm problem from a local duality perspective
- Traps to the BGJT-algorithm for discrete logarithms
- Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
- Discrete logarithm in an arbitrary quotient ring of polynomials of one variable over a finite field
- On the discrete logarithm problem in class groups of curves
- The discrete logarithm problem over prime fields: the safe prime case. The smart attack, non-canonical lifts and logarithmic derivatives.
- scientific article; zbMATH DE number 2127885 (Why is no real title available?)
- scientific article; zbMATH DE number 5575556 (Why is no real title available?)
- On the Complexity of Computing Discrete Logarithms over Algebraic Tori
- scientific article; zbMATH DE number 611186 (Why is no real title available?)
- On an probabilistic algorithm solving discrete logarithm problem
- scientific article; zbMATH DE number 1409225 (Why is no real title available?)
- Computation of a 30750-bit binary field discrete logarithm
- Computing discrete logarithms
- Discrete logarithm diophantiness
- scientific article; zbMATH DE number 7310271 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
- A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
- On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- Cryptography and Coding
- Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
- Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets
- Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation
- A new perspective on the powers of two descent for discrete logarithms in finite fields
- Roots of certain polynomials over finite fields
- Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation
- Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
- On the complexity formulae of the number field sieve and its variants
- A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic
- Utilizing two subfields to accelerate individual logarithm computation in extended tower number field sieve
- Discrete logarithm factory
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
- 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)
