Date:         Fri, 27 Jan 1995 08:31:06 EST
Reply-To:     Francois Morain <morain@polytechnique.fr>
Sender:       Number Theory List <NMBRTHRY@NDSUVM1.BITNET>
From:         Francois Morain <morain@polytechnique.fr>
Subject:      #E(GF(10^499+153))

The number of points on
 
Y^2 = X^3 + 4589 * X + 91228
 
modulo p=10^499+153 is p+1-t where t is
 
                              5531712505360656916297653020318487459872\
3974032546865680659963170112741379929457444426115606162586501422237972\
9340531550358993888032237207379679849162325347608624510817409606791818\
9352121672580436106733206830434953965949226510594406908149864694178969.
 
The algorithm is the Schoof-Elkies-Atkin algorithm. The proof of the
validity of t relies on the method described in [1].
 
Total time was the equivalent of 4200 hours (including 2900 hours for X^p) on
a DEC 3000 - M300X (running with DEC OSF/1 V3.0) 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 computation was made possible by the use of two news ideas of
Dewaghe (Univ. of Lille), see [7]:
 
        1. Suppose l is an Atkin prime, and let r be the degree of the
factors of the modular equation PHI. Then the l-th division polynomial
has a factor of degree (l-1)/2 over GF(p^r) and thus a factor of
degree r*(l-1)/2 over GF(p), by conjugation. This factor is computed
using the Elkies/Atkin approach, over GF(p^r). For example, for l=271,
r=4 and thus we were able to use Schoof original algorithm on a
polynomial of degree 540. Some tricks were used for that, for instance
computing X^(p^2) and Y^(p^2) at the same time, once X^p is known.
Other examples are l=31 and l=41.
 
        2. Suppose l=3 mod 4 is an Elkies prime. Let k be the
eigenvalue associated with a particular factor of degree (l-1)/2,
noted g_l. Let R = Resultant(g_l, X^3 + A X + B) mod p. Then
 
                        (k/l) = (R/p)
 
where (a/p) denotes the Legendre symbole. This formula was used in
combination with M\"uller's idea of "funny" baby-steps/giant-steps for
finding k. Briefly, M\"uller looks for i and j s.t.
 
                        i (X^p, Y^p) = j (X, Y)
 
over the ring Fp[X, Y]/(Y^2 - (X^3+A*X+B)), using only the
X-coordinates and division polynomials for small i and j (plus a fast
comparison algorithm due to Shoup). This yields k = +/- j/i mod l, the
determination of the correct sign being problematic. Dewaghe's theorem
gives the right sign, which gives an obvious speed up when working
with large values of l.
 
Let us remark that Dewaghe's idea can be generalized when l=1 mod 4 and
g_l has a factor of odd degree. Moreover, the central idea can be used also
for the small characteristic case, such as GF(2^n).
 
 
 
 
                    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.
 
[7] L. Dewaghe. Remarques sur l'algorithme SEA. In preparation, dec
1994.
 
#####################################
Below is the repartition E/A, S 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^7 E
3^5 E
5^5 E
7^4 E
11 S
13^3 E
17^2 E
19 S
23^2 E
29^2 E
31 S
37 A 18
41 S
43 A 20
47 E
53 A 18
59 E
61^2 E
67 A 16
71 A 24
73 A 36
79 A 32
83 A 6          *
89 E
97 E
101 E
103 A 48
107 E
109 A 40
113 A 36
127 E
131 E
137 A 44
139 A 48
149 E
151 E
157 E
163 A 40
167 E
173 E
179 E
181 E
191 A 32
193 E
197 E
199 E
211 A 52
223 E
227 E
229 E
233 A 72
239 A 16        *
241 A 110
251 E
257 A 84
263 A 8         *
269 E
271 S
281 A 92
283 A 140
293 A 84
307 A 60
311 E
313 E
317 A 104
331 E
337 E
347 A 56        *
349 E
353 E
359 A 96
367 E
373 E
379 E
383 E
389 E
397 E
401 A 132
409 A 160
419 A 24        *
421 E
431 A 72        *
433 E
439 E
443 E
449 A 120
457 E
461 A
463 E
467 E
479 A
487 A
491 A 80        *
499 E
503 A
509 A
521 E
523 E
541 E
547 E
557 A
563 A
569 E
571 E
577 E
587 E
593 A
599 A
601 A
607 E
613 E
617 E
619 E
631 A
641 E
643 E
647 A
653 E
659 E
661 A
673 A
677 A
683 A
691 E
701 E
709 A
719 E
727 A
733 E
739 A
743 E
751 A
757 A
761 A
773 E
787 A
797 A
809 E
811 E
821 A
823 A
827 E
829 A
839 A
853 E
857 A
859 E
863 A
877 A
881 A
883 E
887 E
907 A
911 E
919 E
929 A
941 A
947 E
953 A
971 E
983 E
991 A