```Date: Fri, 27 Jan 1995 08:31:06 EST Reply-To: Francois Morain Sender: Number Theory List From: Francois Morain 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 ```