Date:         Mon, 3 Oct 1994 10:55:53 EDT
Reply-To:     Francois Morain <morain@polytechnique.fr>
Sender:       Number Theory List <NMBRTHRY@NDSUVM1.BITNET>
From:         Francois Morain <morain@polytechnique.fr>
Subject:      #E(GF(10^399+1311))

The number of points on
 
Y^2 = X^3 + 4589 * X + 91228
 
modulo p=10^399+1311 is p+1-t where t should be
 
          484803054286306900074408166548083255073920278835313909726661\
5677694189516365418745925995646852284383263745461878851419817281736145\
5083335156340880589620894807431883505761714615655125358778325152022526.
 
No legal proof is known, since p+1+-/t do not factor easily. The only proof
is that there was just one match in the match-sort phase.
 
Total time was the equivalent of 1203 hours (including 823 hours for X^p) on
a DEC 2100 (running with DEC OSF/1 V2.1B) on several DEC alpha's of
different types/processors. The match-sort phase took
negligible time. More details are given at the end of this note.
 
This is a technoligical record (almost) only. The algorithm is the
Schoof-(Atkin-)Elkies-Atkin (SEA for short), with some improvements of
Couveignes and FM. The only new theoretical thing is a better
understanding of the pathological cases in the CM algorithm for using
small prime powers (see the case of l=3 below). We refer to the new
version of [3] for this.
 
From a technological point of view, LiPS was used in a better way,
including a tedious stop/resume technique for computing X^p mod PHI:
this enabled us to use stations several workstations which could not
have been used otherwise (this is what we call semi-hostile
environmemt -- machines on which you have to kill your job every
morning and restart it every night, including part of the week-end;
an hostile machine is one on which you must hide yourself to use it :-)).
Unfortunately, this resulted in tremendous problems while tempting to
estimate the running time of all this. The time indicated above is a
lower bound on the (real) total time.
 
Also, some progress was made in polynomial arithmetic for large values
of l.
 
 
                    R. Lercier and F. Morain
 
References:
-----------
 
[1] A. O. L. Atkin, Computing the number of points on an elliptic curve
mod p, draft, notes sent to the NMBRTHRY net, 1988 -- 1992.
 
[2] N. Elkies, Explicit isogenies, 1991.
 
[3] J.-M. Couveignes and F. Morain, Schoof's algorithm and isogeny cycles,
Improved version from the one in the Proc. of ANTS'94, available
shortly.
 
[4] Markus Maurer, Frank Lehmann, Volker Mueller, Victor Shoup, Counting
the number of points on elliptic curves over finite fields of
characteristic greater than three, Proc. ANTS'94.
 
[5] F. Morain, Calcul du nombre de points sur une courbe elliptique
dans un corps fini: aspects algorithmiques, submitted for publication
of the Actes des Journ{\'e}es Arithm{\'e}tiques 1993.
 
[6] R. Schoof, Counting points on elliptic curves over finite fields,
submitted for publication of the Actes des Journ{\'e}es
Arithm{\'e}tiques 1993.
 
#####################################
Below is the repartition E/A, AS meaning a prime was Atkin, but t mod l could
be computed using Schoof original algorithm. A number following an A
means that we computed a restricted set of t mod l using the splitting
of PHI; a * means that this number was used in the match/sort phase.
 
2^5 AS
3^6 E splitting (1x3)
5 AS
7^3 E
11^2 E
13 AS
17^2 E
19 AS
23^2 E
29 A 8
31 A 8
37 A 18
41 A 12 *
43 E
47 A 16
53 E
59 E
61 A 30
67 A 16 *
71 A 12 *
73^2 E
79 A 8 *
83 A 12 *
89^2 E
97 A 42
101 E
103 A 12 *
107^2 E
109 A 40
113 A 18 *
127 A 64
131 A 40
137 E
139 A 48
149 E
151^2 E
157 E
163 E
167 A 12 *
173 A 56
179 E
181 A 72
191 E
193 A 96
197 A 2 *
199 E
211 A 104
223 A 96
227 E
229 A 88
233 A 72
239 E
241 E
251 E
257 A 42 *
263 E
269 A 72
271 E
277 E
281 E
283 E
293 E
307 E
311 A
313 E
317 E
331 E
337 E
347 A
349 E
353 A
359 E
367 E
373 A
379 E
383 E
389 E
397 E
401 A
409 A
419 A
421 E
431 E
433 A
439 E
443 E
449 A
457 E
461 A
463 A
467 A
479 E
487 A
491 E
499 A
503 A
509 A
521 E
523 A
541 E
547 A
557 A
563 A
569 A
571 A
577 A
587 E
593 E
599 A
601 E
607 A
613 E
617 A
619 A
641 E
643 E
647 A
653 A
659 E
661 A
673 E
677 E
683 E
691 E
701 E
719 A
727 A
743 A
751 E
761 A
773 E
797 A
839 E
863 A
911 E
971 A