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
Year:
2015
Laboratories:




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

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)