TY - HEAR
AB - 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.
T1 - A Tale of Two Quasi-Polynomial Algorithms
DA - 2015
AU - Granger, Robert
ID - 215148
UR - http://infoscience.epfl.ch/record/215148/files/UCD_visit_2015.pdf
ER -