home *** CD-ROM | disk | FTP | other *** search
- Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news-out.cwix.com!newsfeed.cwix.com!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!neumann.uwaterloo.ca!alopez-o
- From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
- Newsgroups: sci.math,news.answers,sci.answers
- Subject: sci.math FAQ: Prime Numbers
- Followup-To: sci.math
- Date: 17 Feb 2000 22:51:58 GMT
- Organization: University of Waterloo
- Lines: 328
- Approved: news-answers-request@MIT.Edu
- Expires: Sun, 1 Mar 1998 09:55:55
- Message-ID: <88hu2e$qtn$1@watserv3.uwaterloo.ca>
- Reply-To: alopez-o@neumann.uwaterloo.ca
- NNTP-Posting-Host: daisy.uwaterloo.ca
- Summary: Part 3 of 31, New version
- Originator: alopez-o@neumann.uwaterloo.ca
- Originator: alopez-o@daisy.uwaterloo.ca
- Xref: senator-bedfellow.mit.edu sci.math:347411 news.answers:177531 sci.answers:11239
-
- 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
-