November 26, 2006

The cardinality of the curve E: Y^2 = X^3+4589*X+91128 
modulo (p=10^2499+7131) is p+1-t with

t=  9029293237113248278694915077058747551669321573233
   88302367810581208615756165958894035877574586617277
   34318982519448415619681585331873423864510100420795
   74311991522324244885259324275360356018387099873453
   52419033712773474261605295745613934784827303221928
   19633683575685731860633308594723133404633701650347
   64260993170876499703763557640712637346542861635530
   24856068874723077656097078238737234927413045213588
   59651283907037798537461442232350452753408260919262
   90612524515094221467986424645511793004805487116360
   04743137665795329380558601618835834198796868893391
   29320412135366200684013620964493358896320739874008
   80836072043167819435435301254203874045015052903920
   00068495427393032914624220033239147926141945021241
   22343595679261259560456616043839757898379281360256
   20011798249384004045008584520449871951575828394360
   57153863826221227906256608278950318938988853308125
   78313993269694618112843725345911597786802582642529
   16301362853676864774949480662948026993998954835831
   38776509529714472334869779990628984099436549103356
   97403270607067502491146047484746529420902961132303
   74057634336407195747708572709834152984206107126756
   00846883044490009612881942183199333018689619850760
   29228733382357896594019878760506896270894774907173
   66754410230986360942010122625495852602530360613170

Here are the timings on an AMD 64 Processor 3400+ (2.4GHz), with our NTL
implementation, for some large numbers (excluding the time for
computing modular equations):

what  | 500dd | 1000dd | 1500dd |  1700dd | 2005dd | 2100dd | 2500dd
--------------------------------------------------------------------
X^p   |  6h   | 134h   |  35d   |   60d   | 133d   |   121d | 224d
Total | 10h   | 180h   |  77d   |   80d   | 195d   |   190d | 404d

Elkies's primes took 61 days (not counting X^p mod PHI); isogeny cycles
took 27 days.

Atkin/Schoof's primes (for which the original equation was used on factors of
division polynomials over some GF(p^r)) took 92 days, 26 of which were used
to compute r and discard too large values.

More details can be discovered in the file
http://www.lix.polytechnique.fr/Labo/Francois.Morain/SEA/d2500.t.rebuilt

Among the large values: finding t mod 4111^2, or t mod 3449 where the latter
is an Atkin/Schoof prime.

Modular polynomials were computed using the method of [1]. Isogenies
were computed using [2] and eigenvalue computation was done using [3]
and some of them with the new [4].

	AEnge, FMorain

[1] A. Enge, Computing modular polynomials in quasi-linear time, 
http://www.lix.polytechnique.fr/Labo/Andreas.Enge/vorabdrucke/modcomp.pdf

[2] A. Bostan, F. Morain, B. Salvy, E. Schost, Fast algorithms for
computing isogenies between elliptic curves.
https://hal.inria.fr/inria-00091441

[3] P. Gaudry, F. Morain, Fast algorithms for computing the eigenvalue
in the Schoof-Elkies-Atkin algorithm.
Proceedings ISSAC 2006; http://hal.inria.fr/inria-00001009

[4] P. Mihailescu, Elliptic curve Gauss sums and counting points,
Preprint, 2006. See FM's talk at the Fields Institute
http://www.fields.utoronto.ca/audio/06-07/number_theory/morain/