A Tale of Two Quasi-Polynomial Algorithms

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.

Presented at:
UCD Algebra and Number Theory Seminar, 5th October 2015

 Record created 2016-01-20, last modified 2018-01-28

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)