Galois Theory for DLP

Talk by Prof. Dr. Giacomo Micheli

Date: 12.04.17  Time: 16.00 - 17.00  Room:

In this talk we provide a number theoretical approach to remove the remaining heuristics from the quasi-polynomial time algorithm for discrete logarithm problems in small characteristic (Barbulescu, Gaudry, Joux and Thomé). Informally, one should show that for any finite field F_q and any positive integer k of size roughly q, there exist polynomials f(x) and g(x) in F_q[x] of low degree such that f(x)x^q+g(x) has a factor of degree k.
Introducing a positive parameter d, one can show that a weaker version of the above statement (depending on d) can be converted into a group theoretical problem, which we are able to solve using results by Jordan. It remains to show that d can be chosen small enough.