# A new perspective on the powers of two descent for discrete logarithms in finite fields

@article{Kleinjung2018ANP, title={A new perspective on the powers of two descent for discrete logarithms in finite fields}, author={Thorsten Kleinjung and Benjamin Wesolowski}, journal={IACR Cryptol. ePrint Arch.}, year={2018}, volume={2018}, pages={647} }

A new proof is given for the correctness of the powers of two descent method for computing discrete logarithms. The result is slightly stronger than the original work, but more importantly we provide a unified geometric argument, eliminating the need to analyse all possible subgroups of $\mathrm{PGL}_2(\mathbb F_q)$. Our approach sheds new light on the role of $\mathrm{PGL}_2$, in the hope to eventually lead to a complete proof that discrete logarithms can be computed in quasi-polynomial time… Expand

#### Topics from this paper

#### 2 Citations

Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic

- Computer Science, Mathematics
- IACR Cryptol. ePrint Arch.
- 2019

We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can… Expand

Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

- Computer Science, Mathematics
- IACR Cryptol. ePrint Arch.
- 2019

This paper investigates the practicality of heuristic algorithms based on elliptic bases by using a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms. Expand

#### References

SHOWING 1-10 OF 11 REFERENCES

On the discrete logarithm problem in elliptic curves

- Mathematics
- Compositio Mathematica
- 2010

Abstract We study the elliptic curve discrete logarithm problem over finite extension fields. We show that for any sequences of prime powers (qi)i∈ℕ and natural numbers (ni)i∈ℕ with ni⟶∞ and ni/log… Expand

A general framework for subexponential discrete logarithm algorithms

- Mathematics
- 2002

We describe a generic algorithm for computing discrete logarithms in groups of known order in which a smoothness concept is available. The running time of the algorithm can be proved without using… Expand

On the discrete logarithm problem in finite fields of fixed characteristic

- Mathematics, Computer Science
- IACR Cryptol. ePrint Arch.
- 2015

An algorithm for computing discrete logarithms is presented with which it is proved that for each prime $p$ there exist infinitely many explicit extension fields in which the DLP can be solved in expected quasi-polynomial time. Expand

A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic

- Computer Science, Mathematics
- Selected Areas in Cryptography
- 2013

A new algorithm for discrete logarithms in small characteristic is described based on index calculus and includes two new contributions, including a new method for generating multiplicative relations among elements of a small smoothness basis. Expand

On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in F21971

- Mathematics, Computer Science
- IACR Cryptol. ePrint Arch.
- 2013

A binary field variant of the Joux-Lercier medium-sized Function Field Sieve is proposed, which results not only in complexities as low as \(L_{q^n}(1/3,(4/9)^{1/ 3})\) for computing arbitrary logarithms, but also in an heuristic polynomial time algorithm for finding the discrete logariths when the field has a subfield of an appropriate size. Expand

Generators and irreducible polynomials over finite fields

- Mathematics, Computer Science
- Math. Comput.
- 1997

An application to the distribution of irreducible polynomials is given, which confirms an asymptotic version of a conjecture of Hansen-Mullen about the construction of generators for the multiplicative group of a finite field. Expand

Weil bounds for singular curves

- Mathematics, Computer Science
- Applicable Algebra in Engineering, Communication and Computing
- 2005

These estimates involve the degrees of the polynomials defining the curve set-theoretically, and reduce to Weil's well-known estimate for nonsingular complete intersection curves. Expand

Algebraic geometry

- Computer Science
- Graduate texts in mathematics
- 1977

It’s better to think of Algebraic Geometry as indicating a sub-area of mathematics as a whole, rather than a very precisely defined subfield. Expand

Weil bounds for singular curves, Appl

- Algebra Engrg. Comm. Comput
- 1996

Weil bounds for singular curves, Applicable Algebra in Engineering, Communication and Computing

- 1996