Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

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

Thorsten Kleinjung and Benjamin Wesolowski

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 PGL₂(F_q). Our approach sheds new light on the role of PGL₂, 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.

Published Paper
Talk Slides