mersenneforum.org > Math How did Prof.Cole factor M67?
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-24, 15:00   #1
Neutron3529

Dec 2018
China

1B16 Posts
How did Prof.Cole factor M67?

According to Wiki,
Quote:
 Upon completing the multiplication and demonstrating that the result equaled M67, Cole returned to his seat, not having uttered a word during the hour-long presentation. His audience greeted the presentation with a standing ovation. Cole later admitted that finding the factors had taken "three years of Sundays."
I know that is might be easy to do a trial factor since there are only 162904 primes in the set {a*67+1|a=1,2,3,...,(193707721-1)/67}, hence Cole only needs to try 1045 prime(s) per day, every sunday Cole could takes 40000 seconds and TF quickly, about 40 seconds per prime with TF.

But, how could Cole sieve such prime so efficiently?
Another question is that, what if the factor appears later?
such as the factor of M67 appears like 7618382573*19370772101
I just curious that whether Cole has a efficient TF method so that he could TF M67 in a reasonable time.

2018-12-24, 15:19   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Neutron3529 According to Wiki, I know that is might be easy to do a trial factor since there are only 162904 primes in the set {a*67+1|a=1,2,3,...,(193707721-1)/67}, hence Cole only needs to try 1045 prime(s) per day, every sunday Cole could takes 40000 seconds and TF quickly, about 40 seconds per prime with TF. But, how could Cole sieve such prime so efficiently? Another question is that, what if the factor appears later? such as the factor of M67 appears like 7618382573*19370772101 I just curious that whether Cole has a efficient TF method so that he could TF M67 in a reasonable time.
a, needs be even for 1 thing. It's a/2=k that can range through the natural numbers. Second you can cut down k values using polynomial remainder theorem etc. k and k+3 give the same remainder mod 3 check the first three ( or do modular arithmetic, use the pigeonhole principle etc.) if none of the 2kp+1 divide by 3 then 3 divides none of the candidates at all. Primes that divide into mersennes are 1 or 7 mod 8 so only k that are of certain form need to be checked etc.

https://primes.utm.edu/notes/proofs/MerDiv.html

Last fiddled with by science_man_88 on 2018-12-24 at 15:22

2018-12-24, 15:23   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×532 Posts

Quote:
 Originally Posted by science_man_88 a, needs be even for 1 thing. It's a/2=k that can range through the natural numbers. Second you can cut down k values using polynomial remainder theorem etc. k and k+3 give the same remainder mod 3 check the first three ( or do modular arithmetic, use the pigeonhole principle etc.) if none of the 2kp+1 divide by 3 then 3 divides none of the candidates at all. Primes that divide into mersennes are 1 or 7 mod 8 so only k that are of certain form need to be checked etc. https://primes.utm.edu/notes/proofs/MerDiv.html
Was all that theory available to Cole?

2018-12-24, 15:29   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by retina Was all that theory available to Cole?
The stuff in the link has been known since Euler( see end talk). As to pigeonhole principle etc I think some of it would be but not all.

 2018-12-24, 16:22 #5 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 25428 Posts Cole has written his way: https://projecteuclid.org/download/p...ams/1183417760 so he used TF "without result", after that basically (not named) the Fermat's method.
2018-12-24, 16:39   #6
Dr Sardonicus

Feb 2017
Nowhere

64018 Posts

Quote:
 Originally Posted by R. Gerbicz Cole has written his way: https://projecteuclid.org/download/p...ams/1183417760 so he used TF "without result", after that basically (not named) the Fermat's method.
He used quadratic residues to reduce the list of candidates.

If r is a quadratic residue (mod n) [that is, x^2 == r (mod n) is solvable] then r is automatically a quadratic residue (mod p) for each prime factor p of n. With n = 2^67 - 1, 2 is obviously a quadratic residue (mod n) since 2^67 - 1 = 2*(2^33)^2 -1. Thus, 2 is a quadratic residue modulo every prime factor p of n, so p is congruent to 1 or 7 (mod 8). This condition excludes about half the candidate factors. And, from Cole's 1903 paper to which you have beaten me to providing the link (and which bears the same date as his famous AMS lecture), "ON THE FACTORING OF LAKGE NUMBERS." we have

Quote:
 3. For the number 267 - 1 = 147573952589676412927 I found the following apparently irreducible quadratic remainders: 2, - 3, - 7, 13, -23.53, 37, 41, 61, -67, -71, 23.83, 89, 97, 101, -23.113, -127, 137, 23.151, -23.157, 23.167, 173, 181, 23.191, -23.193, ....
He then describes how he used this information to help find the factors.

BTW, finding this paper involved a search using the parameters

cole methods factoring m67

which seemed obvious for the question being asked. This search quickly led me to the paper's title. Doing another search using

"on the factoring of large numbers" ams 1903

gave a link that led directly to the above link to the pdf of the paper itself. And, saints be praised, it's not an unsearchable image file! I was able to copy-paste text out of it.

 2018-12-24, 16:50 #7 Neutron3529     Dec 2018 China 33 Posts Thank you:) I finally know how he did it. AMAZING!
2018-12-24, 16:57   #8
Neutron3529

Dec 2018
China

33 Posts

Quote:
 Originally Posted by Dr Sardonicus He used quadratic residues to reduce the list of candidates. If r is a quadratic residue (mod n) [that is, x^2 == r (mod n) is solvable] then r is automatically a quadratic residue (mod p) for each prime factor p of n. With n = 2^67 - 1, 2 is obviously a quadratic residue (mod n) since 2^67 - 1 = 2*(2^33)^2 -1. Thus, 2 is a quadratic residue modulo every prime factor p of n, so p is congruent to 1 or 7 (mod 8). This condition excludes about half the candidate factors. And, from Cole's 1903 paper to which you have beaten me to providing the link (and which bears the same date as his famous AMS lecture), "ON THE FACTORING OF LAKGE NUMBERS." we have He then describes how he used this information to help find the factors. BTW, finding this paper involved a search using the parameters cole methods factoring m67 which seemed obvious for the question being asked. This search quickly led me to the paper's title. Doing another search using "on the factoring of large numbers" ams 1903 gave a link that led directly to the above link to the pdf of the paper itself. And, saints be praised, it's not an unsearchable image file! I was able to copy-paste text out of it.
I think you should note that, here, dot (.) means multiply
where -23.53 squals - 23 * 53, not -2353/100.
quite confusing for the first time to meet such symbol
the result is quite the same:

Quote:
 287.1323536760 + 1160932384 = 381015982504 267 - 1 = 3810159825042 - 3808222747832= 193707721 x 761838257287
Here 287.1323536760 means 287*1323536760

 2018-12-25, 20:35 #9 JeppeSN     "Jeppe" Jan 2016 Denmark 8E16 Posts Wikipedia (which you quote) surely also contains Cole's own paper as a reference, with the DOI link https://doi.org/10.1090%2FS0002-9904-1903-01079-9 with which the full-text PDF can be opened. /JeppeSN
 2018-12-25, 21:50 #10 GP2     Sep 2003 50238 Posts In Cole's article, he mentions that Lucas (in 1876) had found M89 to be composite... erroneously, as it turned out. But it was not proven prime until 1911 by Powers, or eight years after Cole did his work on M67 and wrote his article. Good thing he chose to spend his "three years of Sundays" working on M67 instead of M89...
 2018-12-26, 06:48 #11 Neutron3529     Dec 2018 China 33 Posts Thank you. Actually I can't believe that such ancient things could appear on the morden Internet. And then I just treat those reference as some historical research

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 2 2016-11-03 17:00 lfm Data 15 2010-03-30 21:18 fivemack ElevenSmooth 4 2008-05-07 19:28 matt00926 Hardware 3 2005-03-16 00:15 dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 01:40.

Tue Aug 11 01:40:49 UTC 2020 up 24 days, 21:27, 1 user, load averages: 1.97, 2.05, 1.85