Newsgroups: sci.math.research From: morain@seti.inria.fr (morain francois jean) Subject: A new primality record for ECPP Date: Thu, 7 May 1992 13:18:40 GMT Keywords: Primality proving, elliptic curves, partition numbers I have the great pleasure to announce a new primality record for the Elliptic Curve Primality Proving algorithm. Using my distributed implementation, I proved that p(1840926) is prime. This number is a partition number. It has 1505 digits. The CPU time used was approximately the equivalent of 4 years of CPU on a Sun 3/60. The last record was 1226 digits, also with my ECPP program (time was 668 days). More details are given in the following, in form of a FAQ list. A paper on prime values of partition numbers is in preparation. If you need more informations, please email and i'll add it in the FAQ. Francois Morain Laboratoire d'Informatique de l'Ecole Polytechnique (LIX) and INRIA France ------------------------------------------------------------------ More questions on ECPP ------------------------------------------------------------------ Q. What is ECPP? Q. Where can I get the program? Q. Who needs primality proving? Q. How can you test the program? Q. What is a partition number? Q. How what this number selected? Q. What are the characteristics of the record? Q. How does it compare with the Cray record? Q. What is ECPP? ---------------- A. ECPP is a general purpose primality proving algorithm. That means that you input any number and ECPP gives you a *proof* that the number is composite or prime. The theory of this test relies on the properties of elliptic curves modulo p -- in particular the theory of complex multiplication. The program, also called ecpp, gives a certificate of primality, that is a list of numbers implying the primality of the number. An independent verifier can check that the arithmetic properties hold. For more details, we refer to [Atkin-Morain] and [Morain90]. Q. Where can I get the program? ------------------------------- A. The program is available via anonymous ftp from ftp.inria.fr (128.93.1.26) as INRIA/ecpp.V3.4.1.tar.Z. It is written in C and uses the BigNum package, including some assembly routines for sun 3, sparc, dec stations, etc. Q. Who needs primality proving? ------------------------------- A. Everyone interested in number theory, and particularly arithmetic. You can use it also to find prime numbers for cryptographic algorithms. The program proves the primality of 320-bit numbers in less than 2 minutes on a DS3100. Q. How can you test the program? -------------------------------- A. You need large numbers with as the least possible algebraic properties. For instance, numbers b^n-1 are easy to factor and their prime divisors are often congruent to 1 mod n. In the past, I used numbers built up from the digits of pi, e, Euler's constant, etc. They are quite easy to compute, and programs can be found on many computer algebra systems. Partition numbers were introduced in [Rivest91] (see also [LeLeMaPo91]) as benchmarks for factorization of integers. I thought it was a good idea to use them for primality also. However, they are quite technical to compute. Q. What is a partition number? ------------------------------ A. Let n be an integer. Then p(n) counts the number of ways of representing n as a sum of positive integers. For example, 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 and p(5) = 7. The generating function of p(n) is infinity ----- \ n 1 ) p(n) x = ------------------- / infinity ----- --------' n = 0 ' | | m | | (1 - x ) | | | | m = 1 from which one can derive an explicit recurrence relation for p(n) using Euler's identity: p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ... + (-1)^(m-1) p(n-m (3 m - 1)/2) + (-1)^(m-1) p(n - m (3 m + 1)/2) + ... For more details, see the book of Andrews [Andrews76]. Q. How what this number selected? --------------------------------- A. I have computed the values of p(n) in the range n=1800000..1900000 using the preceding formula and the Chinese Remainder Theorem. Then I looked through the values until I found a p(n) which had no small prime factor and was a probable prime. Then, I recomputed p(n) for that particular value using Rademacher's exact formula for p(n) and the properties of it described in the beautiful paper of Lehmer [Lehmer38]. Both values were indentical and I started the program. However, people are encouraged to check my computations. Q. What are the characteristics of the record? ---------------------------------------------- A. 21 workstations were used, located at INRIA and the Ecole Polytechnique. The protocole used is of type master/slaves. A workstation is the master and distributes the tasks using intermediate files. The program running on the master is in LeLisp (this for historical reasons) and all slaves run a C program. The program was started on February, 4th and ended on April, 19th. The certificate is a file of 800 kbytes. The time for verifying the proof is about 26 days of CPU-time-on-a-SUN3/60, to be compared with approximately 1500 for the building of the proof. Q. How does it compare with the Cray record? -------------------------------------------- A. The Cray record is concerned with Mersenne primes, that is prime numbers Mp = 2^p-1 (p a prime). In that particular case, p=756839 yiels a prime number with $227832$ decimal digits. The method they use applies uniquely to numbers N for which N+1 is easily to factor (more precisely, N+1 = h*2^n, with h odd < 2^n). ECPP is a general purpose method that can tackle *any* number. Bibliography ------------ [Andrews76] G. E. Andrews, The theory of Partitions, vol. 2 of Encyclopedia of Mathematics and its Applications, Addison-Wesley, 1976. [Atkin-Morain] Elliptic Curves and Primality Proving. Submitted to Mathematics of Computation, 1990. Also available as INRIA research report, 1256, June 1990. [Lehmer38] D. H. Lehmer, On the series of the partition function. Trans. Amer. Math. Soc., 43, 1938, pp. 271--295. [LeLeMaPo91] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The factorization of the ninth {F}ermat number. To appear, 1991. [Morain90] F. Morain, Courbes elliptiques et tests de primalite', The`se, Universite' de Lyon I, 1990. Also available via anonymous ftp from ftp.inria.fr (128.93.1.26) as INRIA/INRIA-publication/TE-090.tar.Z [Morain92a] F. Morain, Prime values of partition numbers and some new large primes. In preparation, May 1992. [Rivest91] R. Rivest, RSA Factoring Challenge, annoucement dated 10/02/91.