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
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:
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.htmlSee 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=1761References
Mireille Fouquet, Pierrick Gaudry, Robert Harley,
"On Satoh's algorithm and its implementation",
"The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting",