SMS scnews item created by Brendan Creutz at Tue 2 Apr 2013 2228
Type: Seminar
Distribution: World
Expiry: 4 Apr 2013
Calendar1: 4 Apr 2013 1500-1600
CalLoc1: AGR Carslaw 829
Auth: (bcreutz) in SMS-WASM

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 


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).