We would like to provide an update on our work about point-counting of elliptic curves over finite fields using (an extension of) Satoh's algorithm.
First of all, the research report [FGH] that we promised last time is now available from the following URL:
http://www.lix.polytechnique.fr/Labo/Mireille.Fouquet/FGH.ps.gz
And secondly, we have been able to count the points on a curve over GF(2^5003). Let the field be represented as GF(2)[t]/(f(t)) where f(t) is the irreducible polynomial t^5003 + t^18 + t^16 + t^8 + 1. The curve is:
y² + x y = x³ + a6
where the coefficient a6, expressed in hexadecimal, is:
0x3F2065737365727669276C20746961206E6F27757120757672756F7020
2C6E6F63616C6620656C206574726F706D69277551203F20657373657274
EE616D20616C206574726F706D69277571202C746E696F7020646E617267
20656C207473652072656D6941202E6C69656C6F73207561206569762061
6C2074652072756F6D61276C202C74756F74207473652072756F6D61274C
and comes from the ASCII encoding (ISO-8859-1) of the following lines by Alfred de Musset:
L'amour est tout, l'amour et la vie au soleil.
Aimer est le grand point, qu'importe la maîtresse ?
Qu'importe le flacon, pourvu qu'on ait l'ivresse ?
The result we obtained is 2^5003+1-t where:
t = -127341829230648002523018943832226937252103694652076799408922
477612855289377203332779688306682831493273269764054770424297
006136035981001881534370915908800378671831329239996811497697
148968483482544588860921652059893323901220603619128807017820
139267622096926839017765077031279609851645981284832206631534
133807288001526847890199213216628817376092472825902831868662
870338188025136323147277677664022022418918458550932834294111
993858888706282080207793141360407739444174188695573930660771
520813411370625917808763097521316149794711148167469373259091
359932614020803204802726666535109183001470735906486026091062
940240471300907998678966329023873891104882857514851544063170
582653334908271416860233735585623607368617405745505045156736
1750612709555407613790732067510175
We checked that this result is indeed a multiple of the orders of several randomly chosen points on the curve.
The computation took 143 hours using one 750 MHz Alpha processor on an Alpha UP2000 and used 4 GB of memory. We are grateful to Rajit Manohar from Cornell Computer Systems Laboratory who provided the resources needed to establish this record.
With best regards,
Robert Harley