Type: Seminar

Distribution: World

Expiry: 4 Apr 2013

Auth: brendan@60-242-80-51.static.tpgi.com.au (bcreutz) in SMS-WASM

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