New Record in Point Counting on Elliptic Curves in Characteristic 2

Robert Harley Pierrick Gaudry Mireille Fouquet François Morain


We would like to announce the following new record in point counting on elliptic curves. Let E be the curve:
y2 + x y = x3 + a6

over GF(23001). We represent the field as GF(2)[t]/(f(t)) where f is the irreducible polynomial t3001 + t975 + 1. The coefficient a6 we chose is:
0x3F6576EA7220656A20F96F20736973616F276C207361702075742D7365274E

which comes from the ASCII encoding (ISO-8859-1) of the following line by Charles Baudelaire:
N'es-tu pas l'oasis où je rêve?

The result we obtained is 23001 + 1 - t where:

   t = -1440375558254387212517743549792717817521301580
   573304965398721949882182788343602147403338568286117
   602964047438283887869997035112384448200530762524045
   217126405972450445380090498766233236127903809157911
   440678870120793080316394240368567571846194556467373
   415405698362683566256213909170495298430198451525068
   385277025782154636152378895821384422878676537924981
   346430188892662588414041462633112215899534004879953
   9288264207591609255397089053805723638945016394751

We checked that this result is indeed a multiple of the orders of several randomly chosen points on the curve.

The computation took 54 hours using one 667 MHz processor on an AlphaServer ES40 and used 932 MB of memory. We are grateful to Paul Bourke from Swinburne Astrophysics and Supercomputing who graciously provided the CPU time for this record.

The algorithm we used will be described in [FGH] and is a characteristic 2 extension of the algorithm in [Sat], with various improvements and optimisations.

Further details will be available from the following Web page, along with new records as we set them. http://www.lix.polytechnique.fr/Labo/Mireille.Fouquet/elliptic.html

See also Satoh's homepage: http://www.rimath.saitama-u.ac.jp/lab.en/TkkzSatoh/

For comparison, the previous record was set by Frederik Vercauteren in October 1999 for a 1999-bit curve after 65 days of CPU time on 400 MHz PCs using the SEA algorithm. His announcement can be read at: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9910&L=nmbrthry&F=&S=&P=1761

References

Mireille Fouquet, Pierrick Gaudry, Robert Harley,
"On Satoh's algorithm and its implementation",
In preparation.

Takakazu Satoh,
"The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting",
Preprint, 1999.