Computational Algebra Seminar: Donnelly -- Recent techniques for the discrete log problem in finite fields

Speaker: Steve Donnelly (Sydney) 
Title: Recent techniques for the discrete log problem in finite fields 
Time & Place: 3-4pm, Thursday 4 April, AGR Carslaw 829 

PLEASE NOTE CHANGE OF VENUE 

Abstract:
Some startling records were recently announced, by Alain Joux for GF(2^1778)
and GF(2^4080), and by a Dublin group for GF(2^1971).  

I will explain the main ideas involved in the new techniques.  

They developed from special variants of the "medium prime case" of the function field
sieve (Joux + Lercier); this is a particularly simple formulation of the function field
sieve.  The earlier special variants were tricks based on using Kummer extensions, which
would only be applicable for isolated fields.  But these latest techniques apply more
generally, each for a certain class of field.  

Strikingly, Joux’s algorithm has L(1/4,.) complexity whereas comparable algorithms
always had L(1/3,.) at best.  Another novelty in both algorithms is that the main phase
is actually polynomial time while the descent phase is the bottleneck (usually, the
phases are similar).