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 hourlong presentation. His audience greeted the presentation with a standing ovation. Cole later admitted that finding the factors had taken "three years of Sundays."[/QUOTE]I know that is might be easy to do a trial factor since there are only 162904 primes in the set {a*67+1a=1,2,3,...,(1937077211)/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. 
[QUOTE=Neutron3529;503854]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+1a=1,2,3,...,(1937077211)/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.[/QUOTE] 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. [url]https://primes.utm.edu/notes/proofs/MerDiv.html[/url] 
[QUOTE=science_man_88;503855]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.
[url]https://primes.utm.edu/notes/proofs/MerDiv.html[/url][/QUOTE]Was all that theory available to Cole? 
[QUOTE=retina;503856]Was all that theory available to Cole?[/QUOTE]
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. 
Cole has written his way: [url]https://projecteuclid.org/download/pdf_1/euclid.bams/1183417760[/url]
so he used TF "without result", after that basically (not named) the Fermat's method. 
[QUOTE=R. Gerbicz;503864]Cole has written his way: [url]https://projecteuclid.org/download/pdf_1/euclid.bams/1183417760[/url]
so he used TF "without result", after that basically (not named) the Fermat's method.[/QUOTE]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 2[sup]67[/sup]  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, ....[/quote] 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 copypaste text out of it. 
Thank you:)
I finally know how he did it. AMAZING! 
[QUOTE=Dr Sardonicus;503866]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 copypaste text out of it.[/QUOTE] 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 2[SUP]67[/SUP]  1 = 381015982504[SUP]2[/SUP]  380822274783[SUP]2[/SUP]= 193707721 x 761838257287 [/QUOTE]Here 287.1323536760 means 287*1323536760 
Wikipedia (which you quote) surely also contains Cole's own paper as a reference, with the DOI link [url]https://doi.org/10.1090%2FS000299041903010799[/url] with which the fulltext PDF can be opened. /JeppeSN

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... 
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 
All times are UTC. The time now is 01:07. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.