home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / sci-math-faq / primes < prev    next >
Internet Message Format  |  2000-02-18  |  13KB
  1. 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
  2. From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
  3. Newsgroups: sci.math,news.answers,sci.answers
  4. Subject: sci.math FAQ: Prime Numbers
  5. Followup-To: sci.math
  6. Date: 17 Feb 2000 22:51:58 GMT
  7. Organization: University of Waterloo
  8. Lines: 328
  9. Approved: news-answers-request@MIT.Edu
  10. Expires: Sun, 1 Mar 1998 09:55:55
  11. Message-ID: <88hu2e$qtn$1@watserv3.uwaterloo.ca>
  12. Reply-To: alopez-o@neumann.uwaterloo.ca
  13. NNTP-Posting-Host: daisy.uwaterloo.ca
  14. Summary: Part 3 of 31, New version
  15. Originator: alopez-o@neumann.uwaterloo.ca
  16. Originator: alopez-o@daisy.uwaterloo.ca
  17. Xref: senator-bedfellow.mit.edu sci.math:347411 news.answers:177531 sci.answers:11239
  18.  
  19. Archive-name: sci-math-faq/primes
  20. Last-modified: February 20, 1998
  21. Version: 7.5
  22.  
  23.    
  24.                                  Prime Numbers
  25.                                        
  26. Largest known Mersenne prime
  27.  
  28.    Mersenne primes are primes of the form 2^p - 1. For 2^p - 1 to be
  29.    prime we must have that p is prime.
  30.    
  31.    2^(2976221) - 1 is prime. It was discovered in 1997.
  32.    
  33. Largest known prime
  34.  
  35.    The largest known prime is the Mersenne prime described above. The
  36.    largest known non-Mersenne prime, is 391581*2^(216193) - 1, discovered
  37.    by Brown, Noll, Parady, Smith, Smith, and Zarantonello.
  38.    
  39.    Throughout history, the largest known prime has almost always been a
  40.    Mersenne prime; the period between Brown et al's discovery in August
  41.    1989 and Slowinski & Gage's in March 1992 is one of the few
  42.    exceptions.
  43.    
  44.    You can help find more primes. For more information see: The Great
  45.    Internet Mersenne Prime Search home page on http://www.mersenne.org
  46.    
  47.       References
  48.       
  49.    Brown, Noll, Parady, Smith, Smith, and Zarantonello. Letter to the
  50.    editor. American Mathematical Monthly, vol. 97, 1990, p. 214.
  51.    
  52. Largest known twin primes
  53.  
  54.    The two largest known twin primes are 242206083 * 2^38880 +- 1. with
  55.    11713 digits, found by Indlekofer and Ja'rai in November, 1995.
  56.    
  57.    They are also the first known gigantic twin primes (primes with at
  58.    least 10,000 digits).
  59.    
  60.    Recent record holders are:
  61.    
  62.      * 190116*3003*10^(5120) +- 1, with 5129 digits, by Harvey Dubner.
  63.      * 697053813 * 2^(16352) +- 1, with 4932 digits, found by Indlekofer
  64.        and Ja'rai in 1994.
  65.      * 1691232 * 1001 * 10^(4020) +- 1 with 4030 digits, found by H.
  66.        Dubner.
  67.      * 4650828 * 1001 * 10^(3429) +- 1. Found by H. Dubner as well.
  68.        
  69.    The two largest Sophie Germain primes (i.e. p and 2p+1 are both
  70.    primes) are p = 2687145 * 3003 * 10^(5072) - 1 and q=2p + 1, found by
  71.    Harvey Dubner, in October 3, 1995.
  72.    
  73.       References
  74.       
  75.    B. K. Parady and J. F. Smith and S. E. Zarantonello, Smith, Noll and
  76.    Brown. Largest known twin primes. Mathematics of Computation, vol.55,
  77.    1990, pp. 381-382.
  78.    
  79. Largest Fermat number with known factorization
  80.  
  81.    F_(11) = (2^(2^(11))) + 1 which was factored by Brent & Morain in
  82.    1988. F_9 = (2^(2^9)) + 1 = 2^(512) + 1 was factored by A.K. Lenstra,
  83.    H.W. Lenstra Jr., M.S. Manasse & J.M. Pollard in 1990. F_(10) was
  84.    factored by Richard Brent who found a 40-digit factor of 2^(1024) + 1
  85.    on October 20, 1995. The cofactor is a 252 digit number, which is not
  86.    so easy to factor. Luckily, this number was also prime.
  87.    
  88. Algorithms to factor integer numbers
  89.  
  90.    There are several known algorithms that have subexponential estimated
  91.    running time, to mention just a few:
  92.    
  93.      * Continued fraction algorithm.
  94.      * Quadratic sieve algorithm.
  95.      * Class Group method.
  96.      * Elliptic curve algorithm.
  97.      * Number field sieve.
  98.      * Dixon's random squares algorithm.
  99.      * Valle's two-thirds algorithm.
  100.      * Seysen's class group algorithm.
  101.        
  102.       References
  103.       
  104.    A.K. Lenstra, H.W. Lenstra Jr. Algorithms in Number Theory. J. van
  105.    Leeuwen (ed.), Handbook of Theoretical Computer Science, Volume A:
  106.    Algorithms and Complexity Elsevier, pp. 673-715, 1990.
  107.    
  108. Primality Testing
  109.  
  110.    The problem of primality testing and factorization are two distinct
  111.    problems. If we concentrate on primality testing, we never need to
  112.    know the actual factors. The only question to be answered is "is the
  113.    number in question prime or composite."
  114.    
  115.    Wilson's Theorem: The integer p is prime if and only if (p - 1)! is
  116.    congruent to -1 (mod p)
  117.    
  118.    Since there is no known method for rapidly computing (N - 1)! (mod N)
  119.    in, say, log N steps, so Wilson's characterization of primes is of no
  120.    practical value to the testing of the primality of N.
  121.    
  122.    There are many different primality tests and they can be classified in
  123.    at least three different ways:
  124.    
  125.     1. Tests for numbers of special forms
  126.        versus
  127.        Tests for generic numbers
  128.     2. Tests with full justification
  129.        versus
  130.        Tests with justification based on conjectures
  131.     3. Deterministic tests
  132.        versus
  133.        Probabilistic or Monte Carlo tests
  134.        
  135.    Miller's Test
  136.    
  137.    In 1976, G. L. Miller proposed a primality test, which was justified
  138.    using a generalized form of Riemann's hypothesis.
  139.    
  140.    The APR Test
  141.    
  142.    The primality test devised by L. M. Adleman, C. Pomerance and R. S.
  143.    Rumely (1983), also known as the APR test, represents a breakthrough
  144.    because:
  145.    
  146.     1. It is applicable to arbitrary natural numbers N, without requiring
  147.        the knowledge of factors of N - 1 or N + 1.
  148.     2. The running time t(N) is almost polynomial.
  149.     3. The test is justified rigorously, and for the first time ever in
  150.        this domain, it is necessary to appeal to deep results in the
  151.        theory of algebraic numbers; it involves calculations with roots
  152.        of unity and the general reciprocity law for the power residue
  153.        symbol.
  154.        
  155.    The running time of the APR is at the present the world record for a
  156.    deterministic primality test.
  157.    
  158.    Soon afterwards, H. Cohen & A. K. Lenstra (1984) modified the APR
  159.    test, making it more flexible, using Gauss sums in the proof (instead
  160.    of the reciprocity law), and having the new test programmed for
  161.    practical applications. It was the first primality test in existence
  162.    that can routinely handle numbers of up 100 decimal digits, and it
  163.    does so in about 45 seconds.
  164.    
  165.    Monte Carlo methods
  166.    
  167.    Ribenboim mentions three Monte Carlo tests, due to R. Baillie &
  168.    Wagstaff, Jr. (1980), R. Solovay & V. Strassen (1977), and M. O. Rabin
  169.    (1976, 1980).
  170.    
  171.    Elliptic Curves Primality Proving, ECPP
  172.    
  173.    ECPP stands for "Elliptic Curves and Primality Proving". The algorithm
  174.    is described in:
  175.    
  176.     A. O. L. Atkin and F. Morain
  177.     "Elliptic curves and primality proving"
  178.     To appear.
  179.  
  180.    It is a deterministic algorithm that gives a certificate of primality
  181.    for numbers that can be as large as 10**1000 (one thousand).
  182.    
  183.    References
  184.    
  185. [1] A. O. L. Atkin and F. Morain
  186.     "Elliptic curves and primality proving"
  187.     To appear in Math. Comp.
  188.  
  189. %  Lieven Marchand <mal@bewoner.dma.be>
  190.  
  191. [2] F. Morain
  192.     "Courbes elliptiques et tests de primalite'"
  193.     The`se, Universite' de Lyon I, 1990.
  194.     Available at:
  195. http://lix.polytechnique.fr/~morain/english-index.html
  196.  
  197.    This subsection is copyright (C) 1995. Harry J. Smith,
  198.    HJSmith@ix.netcom.com.
  199.    
  200. List of record numbers
  201.  
  202.    Chris Caldwell (caldwell@utm.edu) maintains a list called "The Largest
  203.    Known Primes." Some of the ways to get this list are:
  204.    
  205.     web:     http://www.utm.edu/research/primes/largest.html
  206.     gopher:  unix1.utm.edu, directory 1/user/Public_FTP/pub/math/primes
  207.     ftp:     math.utm.edu, directory /pub/math/primes
  208.  
  209.    Finger primes@math.utm.edu for a few record primes and the current
  210.    ways to get the lists. He would like to know of any new titanic primes
  211.    (over 1000 digits) so that he can add them to his list.
  212.    
  213. What is the current status on Mersenne primes?
  214.  
  215.    The following Mersenne primes are known.
  216.    
  217.  
  218.  
  219.   Number        p                        Year   Discoverer
  220.  
  221.      1-4     2,3,5,7                 pre-1500
  222.      5          13                       1461   Anonymous
  223.      6-7        17,19                    1588   Cataldi
  224.      8          31                       1750   Euler
  225.      9          61                       1883   I.M. Pervushin
  226.     10          89                       1911   Powers
  227.     11          107                      1914   Powers
  228.     12          127                      1876   Lucas
  229.     13-14       521,607                  1952   Robinson
  230.     15-17       1279,2203,2281           1952   R. M. Robinson
  231.     18          3217                     1957   Riesel
  232.     19-20       4253,4423                1961   Hurwitz & Selfridge
  233.     21-23       9689,9941,11213          1963   Gillies
  234.     24          19937                    1971   Tuckerman
  235.     25          21701                    1978   Noll & Nickel
  236.     26          23209                    1979   Noll
  237.     27          44497                    1979   Slowinski & Nelson
  238.     28          86243                    1982   Slowinski
  239.     29          110503                   1988   Colquitt & Welsh
  240.     30          132049                   1983   Slowinski
  241.     31          216091                   1985   Slowinski
  242.     32          756839                   1992   Slowinski & Gage
  243.     33          859433                   1994   Slowinski & Gage
  244.     34          1257787                  1996   Slowinski & Gage
  245.     35          1398269                  1996   Armengaud, Woltman, et. al.
  246.     36?         2976221                  1996   Spence, Woltman, et. al.
  247.  
  248.    The way to determine if 2^p - 1 is prime is to use the Lucas-Lehmer
  249.    test:
  250.    
  251.       Lucas_Lehmer_Test(p):
  252.          u := 4
  253.          for i from 3 to p do
  254.             u := u^2-2 mod 2^p-1
  255.          od
  256.          if u == 0 then
  257.             2^p-1 is prime
  258.          else
  259.             2^p-1 is composite
  260.          fi
  261.  
  262.    All exponents less than 1,481,800 have now been tested at least once.
  263.    
  264.       References
  265.       
  266.    An introduction to the theory of numbers. G.H. Hardy, E.M. Wright.
  267.    Fifth edition, 1979, Oxford.
  268.    
  269. Formulae to compute prime numbers
  270.  
  271.    There is no polynomial which gives all the prime numbers. This is a
  272.    simple exercise to prove.
  273.    
  274.    There is no non-constant polynomial that only takes on prime values.
  275.    The proof is simple enough that an high school student could probably
  276.    discover it. See, for example, Ribenboim's book The Book of Prime
  277.    Number Records.
  278.    
  279.    Note, however, by the work of Jones, Sato, Wada, and Wiens, there is a
  280.    polynomial in 26 variables such that the set of primes coincides with
  281.    the set of positive values taken by this polynomial. See Ribenboim,
  282.    pp. 147-150.
  283.    
  284.    But most people would object to the term ``formula" restricted to mean
  285.    polynomial. Can we not use summation signs, factorial, and the floor
  286.    function in our ``formula"? If so, then indeed, there are formulas for
  287.    the prime numbers. Some of them are listed below.
  288.    
  289.    A reasonable interpretation of the word ``formula" is simply ``Turing
  290.    machine that halts on all inputs". Under this interpretation, there
  291.    certainly are halting Turing machines which compute the n-th prime
  292.    number. However, nobody knows how to compute the n-th prime in time
  293.    polynomial in log n. That's still an open question.
  294.    
  295.    Herb Wilf has addressed the question, ``What is a formula?" in his
  296.    article, ``What is an answer?" which appeared in the American
  297.    Mathematical Monthly, 89 (1982), 289-292. He draws a distinction
  298.    between ``formula" and ``good formula". Anyone who claims ``there is
  299.    no formula for the prime numbers" should read this article.
  300.    
  301.    Here are just a few articles that discuss ``formulas" for primes.
  302.    Almost all of these do not require computation of the primes ahead of
  303.    time. Most of them rely on standard mathematical functions such as
  304.    summation, factorial, greatest integer function, etc.
  305.    
  306.       References
  307.       
  308.    C. Isenkrahe. Math. Annalen 53 (1900), 42-44.
  309.    
  310.    W. H. Mills. Bulletin of the American Mathematical Society 53 (1947),
  311.    604.
  312.    
  313.    L. Moser. Mathematics Magazine 23 (1950), 163-164.
  314.    
  315.    E. M. Wright. American Mathematical Monthly 58 (1951), 616-618.
  316.    (Correction, 59 (1952), 99.)
  317.    
  318.    E. M. Wright. Journal of the London Mathematical Society 29 (1954),
  319.    63-71.
  320.    
  321.    B. R. Srinivasan. Journal of the Indian Mathematical Society 25
  322.    (1961), 33-39.
  323.    
  324.    C. P. Willans. Mathematics Gazette 48 (1964), 413-415.
  325.    
  326.    V. C. Harris. Nordisk Mat. Tidskr. 17 (1969), 82.
  327.    
  328.    U. Dudley. American Mathematical Monthly 76 (1969), 23-28.
  329.    
  330.    C. Vanden Eynden. American Mathematical Monthly 79 (1972), 625.
  331.    
  332.    S. W. Golomb. American Mathematical Monthly 81 (1974), 752-754.
  333.    
  334.    Algorithmic Number Theory. J.O. Shallit, E. Bach. (to be published,
  335.    MIT Press).
  336.    
  337.    A Course in Computational Algebraic Number Theory. Henri Cohen.
  338.    Springer-Verlag, Graduate Texts in Math, 1993.
  339.  
  340.  
  341. -- 
  342. Alex Lopez-Ortiz                                         alopez-o@unb.ca
  343. http://www.cs.unb.ca/~alopez-o                       Assistant Professor    
  344. Faculty of Computer Science                  University of New Brunswick
  345.