Fascinating History of Computation
10 views
Skip to first unread message
Raman Viswanathan
Dec 22, 2008, 9:31:30 AM12/22/08
to nitt...@googlegroups.com, Aliquot, aliquot_...@yahoogroups.com
The Fermat Numbers are the numbers of form F(n) = 2^(2^n)+1.
Only the first 5 numbers, 3, 5, 17, 257, 65537 are known to be prime.
Try associating the length of words with each digit.
Fermat numbers F(5) through F(11) are completely factored.
Fascinating History of Fermat Numbers
After proving that 65537 is prime, Fermat had conjectured that all the subsequent numbers of the form 2^(2^n)+1 will be prime.
The fifth Fermat Number was factored by Euler in 1750 by trial division by proving the fact that any factor of the Fermat Number 2^(2^n)+1 will always be of the form k.2^(n+2)+1, thereby disproving Fermat's conjecture.
The sixth Fermat Number was factored by Landry in 1880.
Since the size of Fermat numbers grow exponentially, new algorithms are required to factor the subsequent Fermat Numbers.
The seventh Fermat number was factored by Morrison and Brillhart in 1970 using the continued fraction method. Factor = 59649589127497217
The eighth Fermat number was factored by Brent and Pollard in 1980 using a variation of the Pollard's Rho method. Factor = 1238926361552897
The next Fermat number to be completely factorized after F(8), was F(11) in 1988 by ECM, since the penultimate prime factor of F(11) is only 22 digits. Indeed the 22 digit factor was found out first before the 21 digit factor. Since ECM is only a probabilistic algorithm, the smaller factor need not necessarily be found first at all. The 564 digit cofactor was verified to be prime by Morain using ECPP subsequently. Smaller factors were already known before.
F(11) = 319489 × 974849 × 167988556341760475137 × 3560841906445833920513 × P564.
The penultimate prime factor of F(9) was found out in 1990 by SNFS, as a large scale distributed computing project. The factor 2424833 was already known before, discovered by Western in 1899.
Factor = 7455602825647884208337395736200454918783366342657
After that, F(10) was the most wanted number. In 1995, Brent found out the 40 digit penultimate prime factor of F(10) by ECM.
F(10) = 45592577 × 6487031809 × 4659775785220018543264560743076778192897 × P252
The twelfth Fermat Number through the twenty fourth Fermat Number, are being incompletely factorized, with all their cofactors being known to be composite. However, no factors are known for F(14), F(20), F(22), F(24).
F(12) = 114689 × 26017793 × 63766529 × 190274191361 × 1256132134125569 × Composite
F(13) = 2710954639361 × 2663848877152141313 × 3603109844542291969 × 319546020820551643220672513 × Composite
F(14) = Composite
F(15) = 1214251009 × 2327042503868417 × 168768817029516972383024127016961 × Composite
F(16) = 825753601 × 188981757975021318420037633 × Composite
F(17) = 31065037602817 × Composite
F(18) = 13631489 × 81274690703860512587777 × Composite
F(19) = 70525124609 × 646730219521 × Composite
F(20) = Composite
F(21) = 4485296422913 × Composite
F(22) = Composite
F(23) = 167772161 × Composite
F(24) = Composite
The twenty fifth Fermat Number through the thirty second Fermat Number, each has atleast one factor known, with the primality of their cofactor being unknown.
F(25) has a factor 25991531462657
F(25) has a factor 204393464266227713
F(25) has a factor 2170072644496392193
F(26) has a factor 76861124116481
F(27) has a factor 151413703311361
F(27) has a factor 231292694251438081
F(28) has a factor 1766730974551267606529
F(29) has a factor 2405286912458753
F(30) has a factor 640126220763137
F(30) has a factor 1095981164658689
F(31) has a factor 46931635677864055013377
F(32) has a factor 25409026523137
The least Fermat Number with unknown status (prime or composite) is currently F(33).
References:
1. How was F6 factored? - by H.C.Williams
2. A method of factoring and the factorization of F7 - by Michael A. Morrison and John Brillhart
3. Factorization of the eighth Fermat Number - by R.P. Brent and J.M. Pollard
4. Factorization of the ninth Fermat Number - by A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard
5. Factorization of the tenth Fermat Number - by R.P. Brent
6. Factorization of the eleventh Fermat Number - by R.P. Brent
History of Mersenne Numbers
Similarly, numbers of the form (2^p)-1 are called Mersenne Numbers. A value of p for which (2^p)-1 is prime is called a Mersenne Prime.
Lucas Lehmer test is used to prove the primality of Mersenne Numbers, as with Pepin's test for Fermat's and Proth's Theorem for Sierpinski and Riesel Numbers.
Any factor of a Mersenne Number M(p) = (2^p)-1 will always be of the form 2kp+1.
Early people believed that if p is prime, then (2^p)-1 will always be prime, but Regius in 1536 showed that M11 = 2047 is not prime, but is 23 × 89.
In 1588, Cataldi proved that M17 and M19 both were prime, and falsely claimed that M23, M29, M31, M37 were also prime. Fermat showed that he was wrong about M23 and M37, and Euler showed that he was wrong about M29 also.
By 1772, Euler proved that M31 was prime, using the fact that any factor of (2^p)-1 will always be of the form 2kp+1.
Later, Mersenne claimed that (2^p)-1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.
Before Electronic Computers
In 1867, Landry proved that [(2^59)-1]/179951 is prime.
In 1876, Lucas proved that (2^127)-1 is prime, using Lucas sequences, the largest prime that stood over for 75 years, until in 1951, Ferrier proved that [(2^148)+1]/17 is prime, by using Proth's Theorem.
After Electronic Computers
With computers, more primes could easily be proved.
For example, in 1951, a computer proved that 180×[(M127)^2]+1, a 79 digit number, is prime.
Since 1952, electronic computers have helped people to discover new Mersenne Primes.
(2^p)-1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 43112609.
The currently largest known prime is (2^43112609)-1. The primes since (2^1398269)-1 were discovered by GIMPS.
The largest prime known since 1952 had always been a Mersenne Prime, except for Amdahl Six, namely 391581.(2^216193)-1 in 1989.
Cunningham Numbers
Similarly, any factor of the Cunningham number [(a^p)-1]/(a-1) will always be of the form 2kp+1, where p is prime and a ≥ 2, except when p is a factor of (a-1). In this case, [(a^p)-1]/(a-1) will be divisible by p itself.
Numbers of the form [(2^p)+1]/3 are called Wagstaff Numbers.
[(2^p)+1]/3 is prime for p = 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321.
Such values of p are called as the Wagstaff Primes.
Numbers of the form [(10^p)-1]/9 are called Repunit Numbers, because they contain only ones in their decimal representation. To be exact and precise, its decimal representation contains, that is, consists of, p number of ones.
[(10^p)-1]/9 is prime for p = 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343.
Such values of p are known as the Repunit Primes.
Only the first 5 numbers, 3, 5, 17, 257, 65537 are known to be prime.
Try associating the length of words with each digit.
65537
Fermat Prime, maybe the largest?
Fermat numbers F(5) through F(11) are completely factored.
Fascinating History of Fermat Numbers
After proving that 65537 is prime, Fermat had conjectured that all the subsequent numbers of the form 2^(2^n)+1 will be prime.
The fifth Fermat Number was factored by Euler in 1750 by trial division by proving the fact that any factor of the Fermat Number 2^(2^n)+1 will always be of the form k.2^(n+2)+1, thereby disproving Fermat's conjecture.
F(5) = 641 × 6700417
Euler's left a broken theorem.. What a tragedy!
The sixth Fermat Number was factored by Landry in 1880.
F(6) = 274177 × 67280421310721
In another case, a product appears.
Since the size of Fermat numbers grow exponentially, new algorithms are required to factor the subsequent Fermat Numbers.
The seventh Fermat number was factored by Morrison and Brillhart in 1970 using the continued fraction method. Factor = 59649589127497217
First exhibitor clever John Brillhart after numerous Saturdays, "I am allowed only primality testing on a weekday.
The eighth Fermat number was factored by Brent and Pollard in 1980 using a variation of the Pollard's Rho method. Factor = 1238926361552897
I am now entirely persuaded to employ Rho method, a handy trick, on gigantic composite numbers.
The next Fermat number to be completely factorized after F(8), was F(11) in 1988 by ECM, since the penultimate prime factor of F(11) is only 22 digits. Indeed the 22 digit factor was found out first before the 21 digit factor. Since ECM is only a probabilistic algorithm, the smaller factor need not necessarily be found first at all. The 564 digit cofactor was verified to be prime by Morain using ECPP subsequently. Smaller factors were already known before.
F(11) = 319489 × 974849 × 167988556341760475137 × 3560841906445833920513 × P564.
The penultimate prime factor of F(9) was found out in 1990 by SNFS, as a large scale distributed computing project. The factor 2424833 was already known before, discovered by Western in 1899.
My next is Alfy Western's old one.
Factor = 7455602825647884208337395736200454918783366342657
MASSIVE TEAM BROKE NINTH FERMAT!
It factored as three primes, June fifteen (forenoon) nineteen nine oh. Actually, one can explain the algorithm quite quickly and easily, er.. Well, space here precludes a detailed account, candidly, the big double search was done by Number Field Sieving!
After that, F(10) was the most wanted number. In 1995, Brent found out the 40 digit penultimate prime factor of F(10) by ECM.
F(10) = 45592577 × 6487031809 × 4659775785220018543264560743076778192897 × P252
The twelfth Fermat Number through the twenty fourth Fermat Number, are being incompletely factorized, with all their cofactors being known to be composite. However, no factors are known for F(14), F(20), F(22), F(24).
F(12) = 114689 × 26017793 × 63766529 × 190274191361 × 1256132134125569 × Composite
F(13) = 2710954639361 × 2663848877152141313 × 3603109844542291969 × 319546020820551643220672513 × Composite
F(14) = Composite
F(15) = 1214251009 × 2327042503868417 × 168768817029516972383024127016961 × Composite
F(16) = 825753601 × 188981757975021318420037633 × Composite
F(17) = 31065037602817 × Composite
F(18) = 13631489 × 81274690703860512587777 × Composite
F(19) = 70525124609 × 646730219521 × Composite
F(20) = Composite
F(21) = 4485296422913 × Composite
F(22) = Composite
F(23) = 167772161 × Composite
F(24) = Composite
The twenty fifth Fermat Number through the thirty second Fermat Number, each has atleast one factor known, with the primality of their cofactor being unknown.
F(25) has a factor 25991531462657
F(25) has a factor 204393464266227713
F(25) has a factor 2170072644496392193
F(26) has a factor 76861124116481
F(27) has a factor 151413703311361
F(27) has a factor 231292694251438081
F(28) has a factor 1766730974551267606529
F(29) has a factor 2405286912458753
F(30) has a factor 640126220763137
F(30) has a factor 1095981164658689
F(31) has a factor 46931635677864055013377
F(32) has a factor 25409026523137
The least Fermat Number with unknown status (prime or composite) is currently F(33).
References:
1. How was F6 factored? - by H.C.Williams
2. A method of factoring and the factorization of F7 - by Michael A. Morrison and John Brillhart
3. Factorization of the eighth Fermat Number - by R.P. Brent and J.M. Pollard
4. Factorization of the ninth Fermat Number - by A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard
5. Factorization of the tenth Fermat Number - by R.P. Brent
6. Factorization of the eleventh Fermat Number - by R.P. Brent
History of Mersenne Numbers
Similarly, numbers of the form (2^p)-1 are called Mersenne Numbers. A value of p for which (2^p)-1 is prime is called a Mersenne Prime.
Lucas Lehmer test is used to prove the primality of Mersenne Numbers, as with Pepin's test for Fermat's and Proth's Theorem for Sierpinski and Riesel Numbers.
Any factor of a Mersenne Number M(p) = (2^p)-1 will always be of the form 2kp+1.
Early people believed that if p is prime, then (2^p)-1 will always be prime, but Regius in 1536 showed that M11 = 2047 is not prime, but is 23 × 89.
In 1588, Cataldi proved that M17 and M19 both were prime, and falsely claimed that M23, M29, M31, M37 were also prime. Fermat showed that he was wrong about M23 and M37, and Euler showed that he was wrong about M29 also.
By 1772, Euler proved that M31 was prime, using the fact that any factor of (2^p)-1 will always be of the form 2kp+1.
Later, Mersenne claimed that (2^p)-1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.
Before Electronic Computers
In 1867, Landry proved that [(2^59)-1]/179951 is prime.
In 1876, Lucas proved that (2^127)-1 is prime, using Lucas sequences, the largest prime that stood over for 75 years, until in 1951, Ferrier proved that [(2^148)+1]/17 is prime, by using Proth's Theorem.
After Electronic Computers
With computers, more primes could easily be proved.
For example, in 1951, a computer proved that 180×[(M127)^2]+1, a 79 digit number, is prime.
Since 1952, electronic computers have helped people to discover new Mersenne Primes.
(2^p)-1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 43112609.
The currently largest known prime is (2^43112609)-1. The primes since (2^1398269)-1 were discovered by GIMPS.
The largest prime known since 1952 had always been a Mersenne Prime, except for Amdahl Six, namely 391581.(2^216193)-1 in 1989.
Cunningham Numbers
Similarly, any factor of the Cunningham number [(a^p)-1]/(a-1) will always be of the form 2kp+1, where p is prime and a ≥ 2, except when p is a factor of (a-1). In this case, [(a^p)-1]/(a-1) will be divisible by p itself.
Numbers of the form [(2^p)+1]/3 are called Wagstaff Numbers.
[(2^p)+1]/3 is prime for p = 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321.
Such values of p are called as the Wagstaff Primes.
Numbers of the form [(10^p)-1]/9 are called Repunit Numbers, because they contain only ones in their decimal representation. To be exact and precise, its decimal representation contains, that is, consists of, p number of ones.
[(10^p)-1]/9 is prime for p = 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343.
Such values of p are known as the Repunit Primes.
Reply all
Reply to author
Forward
0 new messages