Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
2: ANTS XIII
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
 
Other MSP Publications
A new perspective on the powers of two descent for discrete logarithms in finite fields

Thorsten Kleinjung and Benjamin Wesolowski

Vol. 2 (2019), No. 1, 343–352
Abstract

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 PGL2(Fq). Our approach sheds new light on the role of PGL2, in the hope to eventually lead to a complete proof that discrete logarithms can be computed in quasipolynomial time in finite fields of fixed characteristic.

Keywords
discrete logarithm, finite field
Mathematical Subject Classification 2010
Primary: 11Y16
Milestones
Received: 21 February 2018
Revised: 18 June 2018
Accepted: 11 September 2018
Published: 13 February 2019
Authors
Thorsten Kleinjung
Laboratory for Cryptologic Algorithms
School of Computer and Communication Sciences
École Polytechnique Fédérale de Lausanne
Lausanne
Switzerland
Benjamin Wesolowski
Laboratory for Cryptologic Algorithms
School of Computer and Communication Sciences
École Polytechnique Fédérale de Lausanne
Lausanne
Switzerland