Reynald Lercier

[fr]  [en]

Welcome  





Adresse DGA MI

Route de Laillé

35170 Bruz

Adresse

Université de Rennes 1

IRMAR

Équipe Géométrie Algébrique Réelle, Calcul Formel et Cryptographie

Room 612

 

Fax33 2 99 42 64 50
Melreynald.lercier (at) m4x.org
  • open
    close
    Publications
    • • Papers
    • • Talks
  • open
    close
    Software
    • • Magma
  • open
    close
    Computations
    • • Discrete logarithms
    • • Counting points on elliptic curves
    • • Elliptic curves of prescribed order
    • • Counting points on hyperelliptic curves
    • • Integer factorization
Links
ZEN IRMAR
[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, ANTS-V, Sydney, Australia, July 7-12, 2002. Proceedings, volume 2369 of Lecture Notes in Computer Science, pages 431-445. Springer Berlin / Heidelberg, July 2002.

In this paper, we describe improvements to the function field sieve (FFS) for the discrete logarithm problem in GF(pn), 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 Lp^n[1/3,c] = exp( (c+o(1)) log(pn)1/3 log(log(pn))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 AN+/- 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(2521).

[ bib | preprint | publication ] Back

Top


  Site powered by GuppY v4.5.14 © 2004-2005 - CeCILL Free License