Links 


 [JL02] 
A. Joux and R. Lercier. The Function Field Sieve
is quite special.
In C. Fieker and D.R. Kohel, editors,
Algorithmic Number Theory: 5th International Symposium, ANTSV, Sydney,
Australia, July 712, 2002. Proceedings, volume 2369 of Lecture Notes in
Computer Science, pages 431445. Springer Berlin / Heidelberg, July 2002.
In this paper, we describe improvements to the function
field sieve (FFS) for the discrete logarithm problem in
GF(p^{n}), when p is small. Our main contribution is a
new way to build the algebraic function fields needed in the
algorithm. With this new construction, the heuristic
complexity is as good as the complexity of the construction
proposed by Adleman and Huang in 1999, i.e
L_{p^n}[1/3,c] = exp( (c+o(1)) log(p^{n})^{1/3}
log(log(p^{n}))^{2/3}) where c=(32/9)^{1/3}. With
either of these constructions the FFS becomes an equivalent
of the special number field sieve used to factor integers of
the form A^{N}+/ B. From an asymptotic point of view, this
is faster than older algorithm such as Coppersmith's
algorithm and Adleman's original FFS. From a practical
viewpoint, we argue that our construction has better
properties than the construction of Adleman and Huang. We
demonstrate the efficiency of the algorithm by successfully
computing discrete logarithms in a large finite field of
characteristic two, namely GF(2^{521}).
[ bib 
preprint 
publication ]
Back 

