A tale of two quasi-polynomial Algorithms
Title: A tale of two quasi-polynomial Algorithms
Speaker: Robert Granger, (EPFL)
Date: Monday, 5th October 2015
Time: 4pm – 5pm
Location: Agriculture. 1.01 (Seminar Room).
Abstract:
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.
Series: Algebra and Number Theory
Social Media Links