```Date: Mon, 3 Oct 1994 10:55:53 EDT Reply-To: Francois Morain Sender: Number Theory List From: Francois Morain 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 ```