mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-12-24, 15:00   #1
Neutron3529
 
Neutron3529's Avatar
 
Dec 2018
China

110112 Posts
Default 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.
Neutron3529 is offline   Reply With Quote
Old 2018-12-24, 15:19   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Neutron3529 View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-12-24, 15:23   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×3×13×71 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
retina is offline   Reply With Quote
Old 2018-12-24, 15:29   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by retina View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-12-24, 16:22   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25238 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2018-12-24, 16:39   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

52·131 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-24, 16:50   #7
Neutron3529
 
Neutron3529's Avatar
 
Dec 2018
China

33 Posts
Default

Thank you:)
I finally know how he did it.
AMAZING!
Neutron3529 is offline   Reply With Quote
Old 2018-12-24, 16:57   #8
Neutron3529
 
Neutron3529's Avatar
 
Dec 2018
China

110112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
Neutron3529 is offline   Reply With Quote
Old 2018-12-25, 20:35   #9
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

23·3·5 Posts
Smile

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
JeppeSN is offline   Reply With Quote
Old 2018-12-25, 21:50   #10
GP2
 
GP2's Avatar
 
Sep 2003

1010000100112 Posts
Default

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...
GP2 is offline   Reply With Quote
Old 2018-12-26, 06:48   #11
Neutron3529
 
Neutron3529's Avatar
 
Dec 2018
China

33 Posts
Default

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
Neutron3529 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Got an email from prof. Keller ET_ FermatSearch 2 2016-11-03 17:00
big factor lfm Data 15 2010-03-30 21:18
New factor fivemack ElevenSmooth 4 2008-05-07 19:28
Prime 95 + BSOD issues Win xp Prof sp2 matt00926 Hardware 3 2005-03-16 00:15
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 07:52.

Sun Jul 12 07:52:25 UTC 2020 up 109 days, 5:25, 0 users, load averages: 1.83, 1.81, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.