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
[JL01]

A. Joux and R. Lercier. “Chinese & Match”, an alternative to Atkin's “Match and Sort” method used in the SEA algorithm. Mathematics of Computation, 70(234):827-836, April 2001.

A classical way to compute the number of points of elliptic curves defined over finite fields from partial data obtained in SEA (Schoof Elkies Atkin) algorithm is a so-called “Match and Sort” method due to Atkin. This method is a “baby step/giant step” way to find the number of points among C candidates with O(sqrt(C)) elliptic curve additions. Observing that the partial information modulo Atkin's primes is redundant, we propose to take advantage of this redundancy to eliminate the usual elliptic curve algebra in this phase of the SEA computation. This yields an algorithm of similar complexity, but the space needed is smaller than what Atkin's method requires. In practice, our technique amounts to an acceleration of Atkin's method, allowing us to count the number of points of an elliptic curve defined over GF(21663). As far as we know, this is the largest point-counting computation to date. Furthermore, the algorithm is easily parallelized.

[ bib | preprint | publication ] Back

Top


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