From: HJSmith@ix.netcom.com (Harry J. Smith) Newsgroups: sci.math Subject: Re: Perfect primality test? Date: 4 Apr 1995 11:51:00 GMT In <3lp1q3$bi5@mercury.kingston.ac.uk> k941319@kingston.ac.uk (Paul Giaccone) writes: > >Marc Plumb (mplumb@sciborg.uwaterloo.ca) wrote: >: Is there a primality test that is thought/known to be perfect? >: Obviously trying to divide by everything smaller will work, but I >: was hoping to find something a little faster. > >I don't know about Maple's test. The sieve of Erastothenes is certainly >perfect. I am not aware of any other non-deterministic primality tests >(which is essentially what you are asking for); in their absence, the >answer to your question is, theoretically, no. > >-- >=========================================================================== >Paul Giaccone | "In Brussels, anything is possible if you believe >k941319@kingston.ac.uk | carrots are a fruit and bananas should be > | straight." - The Rt Hon Michael Portillo MP >=========================================================================== Much of what I know about this subject comes from the book by Paulo Ribenboim, "The Little Book of Big Primes" Springer Verlag, New York, 1991. The problem of primality testing and factorization are two distinct problems. If we concentrate on primality testing, we never need to know the actual factors. The only question to be answered is "is the number in question prime or composite." Wilson's Theorem: The integer p is prime if and only if (p-1)! is congruent to -1 (mod p) Since there is no known method for rapidly computing (N-1)! (mod N) in, say, log N steps, so Wilson's characterization of primes is of no practical value to the testing of the primality of N. Lucas-Lehmer Primality test for Mersenne Numbers: The way to determine if 2^p-1 is prime is to use the Lucas-Lehmer test: Lucas_Lehmer_Test(p): u := 4 for i from 3 to p do u := u^2-2 mod 2^p-1 od if u == 0 then 2^p-1 is prime else 2^p-1 is composite fi There are many different primality tests and they can be classified in at least three different ways: 1. Tests for numbers of special forms verses Tests for generic numbers 2. Tests with full justification verses Tests with justification based on conjectures 3. Deterministic tests verses Probabilistic or Monte Carlo tests Miller's Test In 1976, G. L. Miller proposed a primality test, which was justified using a generalized form of Riemann's hypothesis. The APR Test The primality test devised by L. M. Adleman, C. Pomerance and R. S. Rumely (1983), also known as the APR test, represents a breakthrough because: (i) It is applicable to arbitrary natural numbers N, without requiring the knowledge of factors of N - 1 or N + 1. (ii) The running time t(N) is almost polynomial. (iii) The test is justified rigorously, and for the first time ever in this domain, it is necessary to appeal to deep results in the theory of algebraic numbers; it involves calculations with roots of unity and the general reciprocity law for the power residue symbol. The running time of the APR is at the present the world record for a deterministic primality test. Soon afterwards, H. Cohen & A. K. Lenstra (1984) modified the APR test, making it more flexible, using Gauss sums in the proof (instead of the reciprocity law), and having the new test programmed for practical applications. It was the first primality test in existence that can routinely handle numbers of up 100 decimal digits, and it does so in about 45 seconds. Monte Carlo methods Ribenboim mentions three Monte Carlo tests, due to R. Baillie & Wagstaff, Jr. (1980), R. Solovay & V. Strassen (1977), and M. O. Rabin (1976, 1980). Elliptic Curves Primality Proving, ECPP ECPP stands for "Elliptic Curves and Primality Proving". The algorithm is described in: A. O. L. Atkin and F. Morain "Elliptic curves and primality proving" To appear. It is a deterministic algorithm that gives a certificate of primality for numbers that can be as large as 10**1000 (one thousand). Bibliography on ECPP -------------------- [1] A. O. L. Atkin and F. Morain "Elliptic curves and primality proving" To appear in Math. Comp. [2] F. Morain "Courbes elliptiques et tests de primalite'" The`se, Universite' de Lyon I, 1990. Available as TE-INRIA-090.tar.Z via anoymous ftp from nuri.inria.fr (128.93.1.26), in the directory IRIA/INRIA-publication. -- | Harry J. Smith | 19628 Via Monte Dr., Saratoga, CA 95070-4522, USA | Home Phone: 408 741-0406, Work Phone: 408 235-5088 (Voice Mail) | EMail: HJSmith@ix.netcom.com on the Internet via Netcom NetCruiser -- ============================================================================== Newsgroups: sci.math From: dik@cwi.nl (Dik T. Winter) Subject: Re: Perfect primality test? Date: Tue, 4 Apr 1995 15:01:45 GMT In article <3lrbr4$clk@ixnews4.ix.netcom.com> HJSmith@ix.netcom.com (Harry J. Smith) writes: > Soon afterwards, H. Cohen & A. K. Lenstra (1984) modified the APR test, > making it more flexible, using Gauss sums in the proof (instead of the > reciprocity law), and having the new test programmed for practical > applications. It was the first primality test in existence that can > routinely handle numbers of up 100 decimal digits, and it does so in > about 45 seconds. > Those 100 digits and 45 seconds are figures from 1984! With current machines it is much faster. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl ============================================================================== From: desnogue@unice.fr (Laurent.DESNOGUES) Newsgroups: sci.math Subject: Re: Perfect primality test? Date: 05 Apr 1995 07:10:20 GMT > Soon afterwards, H. Cohen & A. K. Lenstra (1984) modified the APR test, > making it more flexible, using Gauss sums in the proof (instead of the > reciprocity law), and having the new test programmed for practical > applications. Small mistake: the improved APR by Cohen and Lenstra uses Jacobi sums. The test has since been improved by Wieb Bosma. -- Laurent Desnogues