The cardinality of the curve E: Y^2 = X^3+4589*X+91128
modulo (p=10^1499+2001) is p+1-t with
t=-33869807502019604962429491732215909675312109702927
38256660675992888798047358665277537955891121925282
04312584535186270889492848925526604477183857980923
59477665742381275305428214011551504715014013677567
26419740446725166854919715964302583573538365053023
79848948669059223574594199242770519859918901305463
56315123760066014938693077158287600028457826986887
95318782320991052056671119858045473657308508388388
25841475058655269609931826424414231889685224914589
24896470910210262180251945525555489587430454422785
21589418839490929443491392338326471404212463987422
20667685409798264040019116263291700594455504306667
01089059814033633752435141603224931835752822032445
78882193392994255212234498834012240698002236270116
43294029774897132053258354006762051244824374486430
Why perform such a computation? It was tempting to measure the impact
of technology on the feasability of such a computation using the
classical SEA algorithm. After all, the preceding record of 500
decimal digits was done 10 years ago [1].
Rewriting the program in NTL, we get the following equivalent
cumulated CPU time on an AMD 64 Processor 3400+ (2.4GHz):
500dd 10 hours
1000dd 180 hours
1500dd 6400 hours
These timings do not take into account the time needed to compute the
relevant modular equations. However, during the computations for the
1000dd, it appeared that computing these equations was more and more
costly, the reason being that the classical O(ell^4) method using
series expansions and chinese primes was just too slow. Fortunately,
one of us (AE) came in with a new faster method. Briefly, one looks
for the modular equation of some function built from Hecke operators
T_r, as described for instance in Mueller's thesis. The complexity of
AE's method is then O(r ell^3), which is much faster than O(ell^4), if
r is small, which happens very frequently. More details are given in
AE's forthcoming paper. We content ourselves with just one numerical
example. For the prime ell = 2713, it took 41 hours to compute the
modular equation. This should be compared to the 3 hours required to
compute X^p mod Phi_2713 and to the 3 more for performing the
remaining computations.
As can be seen from the data file [2], some effort was put in finding
t mod ell for Atkin primes that are sometimes rather large, using the
techniques of Dewaghe.
AEnge, PGaudry and FMorain
[1] http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind9501&L=nmbrthry&P=R503
[2] http://www.lix.polytechnique.fr/Labo/Francois.Morain/SEA/d1500x.t