Vol. 2, 2019

Download this article
Download this article For screen
For printing
Recent Volumes
5: Gauge Theory and Low-Dimensional Topology
4: ANTS XIV
3: Hillman: Poincaré Duality
2: ANTS XIII
1: ANTS X
The Open Book Series
All Volumes
 
About the Series
Ethics Statement
Purchase Printed Copies
Author Index
 
ISSN 2329-907X (online)
ISSN 2329-9061 (print)
 
MSP Books and Monographs
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