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:

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

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.

See also Satoh's homepage:

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:


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.