Publication
In 2013 the Discrete Logarithm Problem in finite fields of small characteristic enjoyed a rapid series of developments, starting with the heuristic polynomial-time relation generation method due to Gologlu, Granger, McGuire and Zumbragel, and culminating with the first heuristic quasi-polynomial algorithm (QPA) due to Barbulescu, Gaudry, Joux and Thome, which built upon an approach due to Joux. In 2014 Granger, Kleinjung and Zumbragel devised a way to extend the original GGMZ approach, resulting in a completely new QPA which has some interesting properties; in particular in some families of fields one can rigorously prove the complexity. In this talk we review these developments and compare the two QPAs.
Arjen Lenstra, Robert Granger, Thorsten Kleinjung, Benjamin Pierre Charles Wesolowski