How did Prof.Cole factor M67?

[Neutron3529]

According to Wiki,

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.

[science_man_88]

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

[retina]

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?

[science_man_88]

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.

[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.

[Dr Sardonicus]

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

3. For the number 2⁶⁷ - 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.

[Neutron3529]

Thank you:)
I finally know how he did it.
AMAZING!

[Neutron3529]

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:

287.1323536760 + 1160932384 = 381015982504
2⁶⁷ - 1 = 381015982504² - 380822274783²= 193707721 x 761838257287

Here 287.1323536760 means 287*1323536760

[JeppeSN]

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

[GP2]

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...

[Neutron3529]

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