[Comp.Sci.Dept, Utrecht] Note from archiver<at>cs.uu.nl: This page is part of a big collection of Usenet postings, archived here for your convenience. For matters concerning the content of this page, please contact its author(s); use the source, if all else fails. For matters concerning the archive as a whole, please refer to the archive description or contact the archiver.

Subject: sci.math FAQ: Prime Numbers

This article was archived around: 17 Feb 2000 22:51:58 GMT

All FAQs in Directory: sci-math-faq
All FAQs posted in: sci.math
Source: Usenet Version


Archive-name: sci-math-faq/primes Last-modified: February 20, 1998 Version: 7.5
Prime Numbers Largest known Mersenne prime Mersenne primes are primes of the form 2^p - 1. For 2^p - 1 to be prime we must have that p is prime. 2^(2976221) - 1 is prime. It was discovered in 1997. Largest known prime The largest known prime is the Mersenne prime described above. The largest known non-Mersenne prime, is 391581*2^(216193) - 1, discovered by Brown, Noll, Parady, Smith, Smith, and Zarantonello. Throughout history, the largest known prime has almost always been a Mersenne prime; the period between Brown et al's discovery in August 1989 and Slowinski & Gage's in March 1992 is one of the few exceptions. You can help find more primes. For more information see: The Great Internet Mersenne Prime Search home page on http://www.mersenne.org References Brown, Noll, Parady, Smith, Smith, and Zarantonello. Letter to the editor. American Mathematical Monthly, vol. 97, 1990, p. 214. Largest known twin primes The two largest known twin primes are 242206083 * 2^38880 +- 1. with 11713 digits, found by Indlekofer and Ja'rai in November, 1995. They are also the first known gigantic twin primes (primes with at least 10,000 digits). Recent record holders are: * 190116*3003*10^(5120) +- 1, with 5129 digits, by Harvey Dubner. * 697053813 * 2^(16352) +- 1, with 4932 digits, found by Indlekofer and Ja'rai in 1994. * 1691232 * 1001 * 10^(4020) +- 1 with 4030 digits, found by H. Dubner. * 4650828 * 1001 * 10^(3429) +- 1. Found by H. Dubner as well. The two largest Sophie Germain primes (i.e. p and 2p+1 are both primes) are p = 2687145 * 3003 * 10^(5072) - 1 and q=2p + 1, found by Harvey Dubner, in October 3, 1995. References B. K. Parady and J. F. Smith and S. E. Zarantonello, Smith, Noll and Brown. Largest known twin primes. Mathematics of Computation, vol.55, 1990, pp. 381-382. Largest Fermat number with known factorization F_(11) = (2^(2^(11))) + 1 which was factored by Brent & Morain in 1988. F_9 = (2^(2^9)) + 1 = 2^(512) + 1 was factored by A.K. Lenstra, H.W. Lenstra Jr., M.S. Manasse & J.M. Pollard in 1990. F_(10) was factored by Richard Brent who found a 40-digit factor of 2^(1024) + 1 on October 20, 1995. The cofactor is a 252 digit number, which is not so easy to factor. Luckily, this number was also prime. Algorithms to factor integer numbers There are several known algorithms that have subexponential estimated running time, to mention just a few: * Continued fraction algorithm. * Quadratic sieve algorithm. * Class Group method. * Elliptic curve algorithm. * Number field sieve. * Dixon's random squares algorithm. * Valle's two-thirds algorithm. * Seysen's class group algorithm. References A.K. Lenstra, H.W. Lenstra Jr. Algorithms in Number Theory. J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity Elsevier, pp. 673-715, 1990. Primality Testing 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. There are many different primality tests and they can be classified in at least three different ways: 1. Tests for numbers of special forms versus Tests for generic numbers 2. Tests with full justification versus Tests with justification based on conjectures 3. Deterministic tests versus 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: 1. It is applicable to arbitrary natural numbers N, without requiring the knowledge of factors of N - 1 or N + 1. 2. The running time t(N) is almost polynomial. 3. 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). References [1] A. O. L. Atkin and F. Morain "Elliptic curves and primality proving" To appear in Math. Comp. % Lieven Marchand <mal@bewoner.dma.be> [2] F. Morain "Courbes elliptiques et tests de primalite'" The`se, Universite' de Lyon I, 1990. Available at: http://lix.polytechnique.fr/~morain/english-index.html This subsection is copyright (C) 1995. Harry J. Smith, HJSmith@ix.netcom.com. List of record numbers Chris Caldwell (caldwell@utm.edu) maintains a list called "The Largest Known Primes." Some of the ways to get this list are: web: http://www.utm.edu/research/primes/largest.html gopher: unix1.utm.edu, directory 1/user/Public_FTP/pub/math/primes ftp: math.utm.edu, directory /pub/math/primes Finger primes@math.utm.edu for a few record primes and the current ways to get the lists. He would like to know of any new titanic primes (over 1000 digits) so that he can add them to his list. What is the current status on Mersenne primes? The following Mersenne primes are known. Number p Year Discoverer 1-4 2,3,5,7 pre-1500 5 13 1461 Anonymous 6-7 17,19 1588 Cataldi 8 31 1750 Euler 9 61 1883 I.M. Pervushin 10 89 1911 Powers 11 107 1914 Powers 12 127 1876 Lucas 13-14 521,607 1952 Robinson 15-17 1279,2203,2281 1952 R. M. Robinson 18 3217 1957 Riesel 19-20 4253,4423 1961 Hurwitz & Selfridge 21-23 9689,9941,11213 1963 Gillies 24 19937 1971 Tuckerman 25 21701 1978 Noll & Nickel 26 23209 1979 Noll 27 44497 1979 Slowinski & Nelson 28 86243 1982 Slowinski 29 110503 1988 Colquitt & Welsh 30 132049 1983 Slowinski 31 216091 1985 Slowinski 32 756839 1992 Slowinski & Gage 33 859433 1994 Slowinski & Gage 34 1257787 1996 Slowinski & Gage 35 1398269 1996 Armengaud, Woltman, et. al. 36? 2976221 1996 Spence, Woltman, et. al. 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 All exponents less than 1,481,800 have now been tested at least once. References An introduction to the theory of numbers. G.H. Hardy, E.M. Wright. Fifth edition, 1979, Oxford. Formulae to compute prime numbers There is no polynomial which gives all the prime numbers. This is a simple exercise to prove. There is no non-constant polynomial that only takes on prime values. The proof is simple enough that an high school student could probably discover it. See, for example, Ribenboim's book The Book of Prime Number Records. Note, however, by the work of Jones, Sato, Wada, and Wiens, there is a polynomial in 26 variables such that the set of primes coincides with the set of positive values taken by this polynomial. See Ribenboim, pp. 147-150. But most people would object to the term ``formula" restricted to mean polynomial. Can we not use summation signs, factorial, and the floor function in our ``formula"? If so, then indeed, there are formulas for the prime numbers. Some of them are listed below. A reasonable interpretation of the word ``formula" is simply ``Turing machine that halts on all inputs". Under this interpretation, there certainly are halting Turing machines which compute the n-th prime number. However, nobody knows how to compute the n-th prime in time polynomial in log n. That's still an open question. Herb Wilf has addressed the question, ``What is a formula?" in his article, ``What is an answer?" which appeared in the American Mathematical Monthly, 89 (1982), 289-292. He draws a distinction between ``formula" and ``good formula". Anyone who claims ``there is no formula for the prime numbers" should read this article. Here are just a few articles that discuss ``formulas" for primes. Almost all of these do not require computation of the primes ahead of time. Most of them rely on standard mathematical functions such as summation, factorial, greatest integer function, etc. References C. Isenkrahe. Math. Annalen 53 (1900), 42-44. W. H. Mills. Bulletin of the American Mathematical Society 53 (1947), 604. L. Moser. Mathematics Magazine 23 (1950), 163-164. E. M. Wright. American Mathematical Monthly 58 (1951), 616-618. (Correction, 59 (1952), 99.) E. M. Wright. Journal of the London Mathematical Society 29 (1954), 63-71. B. R. Srinivasan. Journal of the Indian Mathematical Society 25 (1961), 33-39. C. P. Willans. Mathematics Gazette 48 (1964), 413-415. V. C. Harris. Nordisk Mat. Tidskr. 17 (1969), 82. U. Dudley. American Mathematical Monthly 76 (1969), 23-28. C. Vanden Eynden. American Mathematical Monthly 79 (1972), 625. S. W. Golomb. American Mathematical Monthly 81 (1974), 752-754. Algorithmic Number Theory. J.O. Shallit, E. Bach. (to be published, MIT Press). A Course in Computational Algebraic Number Theory. Henri Cohen. Springer-Verlag, Graduate Texts in Math, 1993. -- Alex Lopez-Ortiz alopez-o@unb.ca http://www.cs.unb.ca/~alopez-o Assistant Professor Faculty of Computer Science University of New Brunswick