How did Prof.Cole factor M67?

[Neutron3529]

Let me explain what Prof. Cole do:
Firstly, Prof. Cole sieve for some quadratic residues.
the sieve step might be very difficult, I believe that it took about 90% the time for Prof. Cole to factor 2^67-1.


It could not be human-friendly to reproduce such step, here I will give some example using Pari/GP:


> n=2^67-1
> factor(((-(sqrtnint(n,2))^2))%n)
[ 2 1]
[ 3 2]
[ 23 1]
[ 37 2]
[ 83 1]
[467 1]


so that -2*3^2*23*37^2*83*467 is a quadratic remainder, furthermore, -2*23*83*467 is also a quadratic remainder.


Here continue fraction may helpful for search:


> a(t)=my(tmp=contfracpnqn(contfrac(sqrtn(n,2),t)));tmp[1,1]*=tmp[1,1];tmp[2,2]*=tmp[2,2];tmp[1,2]*=tmp[1,2];tmp[2,1]*=tmp[2,1];([1,-n]*tmp)[1]
(sorry for such ugly handwritten code)
> factor(a(1280))~
[3 7 23 83 127]
[4 3 1 1 1]

> factor(a(1494))~
[2 3 7 127 331]
[1 1 5 1 1]


> factor(a(1658))~
[2 7 13 101 239]
[1 5 1 1 1]


> factor(a(1986))~
[2 3 89 137 151 191]
[1 2 1 1 1 1]


...
I think Prof. Cole may have his own efficient way to do such search.
finally he found some 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, ....



things could be very easy since then:
if we know -3 is a quadratic remainder mod 2^67-1, p|2^67-1 ,then 3 should be a quadratic remainder of p
further more, using quadratic reciprocity law, if p mod4=1, p should be a quadratic remainder of 3, otherwise p should be not.
notice that 3 is also a quadratic remainder of q=n/p , for each p, we could calculate whether q=n/p is also a quadratic remainder, here each new remainder we use will eliminate 3/4 of the factors.
so that Prof. Cole could suddenly find the result.

[Greybeard]

I understand that this is tangential to the original question that began this thread, but it seemed (to me) like a reasonable extension.

Of course, I've seen his reported estimate that he spent "three years of Sundays," and in that, I find teachable lessons on the virtues of perseverance, diligence, and intellectual curiosity.

I'm trying to come up with a way to make his effort clearer to youth who have never known what it was like to do math before smart phones and computers - even scientific calculators seem quaint and fusty now. So I was wondering if anyone has any data/estimates on how long it would have taken to factor a 21-digit semiprime if Cole had had a modern PC and modern factoring algorithms available to him. I'm not thinking about quantum computers or even supercomputers, just a high-end desktop with general processors like the ones that families might have in their homes.

A few further thoughts: first, something about "beggars and choosers" comes to mind when I'm searching for some information that I'm not even certain how to define cleanly. So I'll take whatever I can get.

Another thought is that although I was a math major for a period in my wild-and-ill-spent-youth (which in my case, is pretty much all one word), I haven't used any higher math in decades, so please try not to over-assume my current computational competence.

And finally, if there is someplace that you think I should look - either for this particular question or for other ways that I might make Cole's effort and determination more relatable today - please feel free to simply send me a link. I'll gladly fetch the information myself; I just haven't been able to find it yet on my own.



All suggestions/guidance is welcome. I've read a number of accounts of Cole's life in general, and of his M67 work in particular, but I still feel that there is much that I haven't yet uncovered.

[R.D. Silverman]

Originally Posted by Greybeard

I understand that this is tangential to the original question that began this thread, but it seemed (to me) like a reasonable extension.

Of course, I've seen his reported estimate that he spent "three years of Sundays," and in that, I find teachable lessons on the virtues of perseverance, diligence, and intellectual curiosity.

I'm trying to come up with a way to make his effort clearer to youth who have never known what it was like to do math before smart phones and computers - even scientific calculators seem quaint and fusty now. So I was wondering if anyone has any data/estimates on how long it would have taken to factor a 21-digit semiprime if Cole had had a modern PC and modern factoring algorithms available to him.

A few milliseconds.

Cole did it via Fermat's method with exclusion moduli.

[Greybeard]

Wow! Thanks. That was sure fast enough, and spot on point.

Maybe beggars can be choosers.

[chris2be8]

chris@rigel:~/bin$ time yafu 'siqs(2^67-1)'




***factors found***

P12 = 761838257287
P9 = 193707721

ans = 1


real	0m0.135s
user	0m0.088s
sys	0m0.028s

That was using 1 core on a fairly slow system, doing other work in the background. But it still took less time than it took me to read the result on the screen.

Chris

[LaurV]

Pari, Trial Factoring with 420 classes (script posted here in the past), slow/moderate laptop (i5-3340M at 2.7GHz)

gp > tf_420c_s(67)
M67 has a factor: 193707721
time = 234 ms.
%1 = 193707721
gp >

[CRGreathouse]

If you're willing to put in several minutes into optimizing your runtime, you can shave off a few more milliseconds.

echo 147573952589676412927 | ./ecm -q -c 5 -one 650

factors it in about 6 milliseconds on one core of my old desktop (i7-5820K). You don't often see a B1 that size.

[R.D. Silverman]

Originally Posted by CRGreathouse

If you're willing to put in several minutes into optimizing your runtime, you can shave off a few more milliseconds.

echo 147573952589676412927 | ./ecm -q -c 5 -one 650

factors it in about 6 milliseconds on one core of my old desktop (i7-5820K). You don't often see a B1 that size.

I did say "a few milliseconds". But of course, no one listens.

[axn]

Originally Posted by R.D. Silverman

I did say "a few milliseconds". But of course, no one listens.

Are you seriously salty at people for being curious?!

[R.D. Silverman]

Originally Posted by axn

Are you seriously salty at people for being curious?!

Did I gore your ox, too?

[LaurV]

Our goal was not to get the fastest factoring method, but to show that even such non-efficient stuff like TF (which is in fact what Mr. Cole used) would factor M67 in "milliseconds" in an average computer. That is what the OP wanted to know.

With the same slow laptop:

gp > \r pollard_rho
gp > rho(67)
time = 11 ms.
%1 = 193707721
gp > prho(67,3)
time = 27 ms.
%2 = 193707721
gp > \r pollardq
gp > mpm1(67)

Factoring M67 ...
        Beginning First Stage P-1 of M67 ...
           Base     = 3
           B1 Limit = 100000
           B2 Limit = 5000000
        First Stage completed, GCD is M67.
        Use smaller B1 bound, or take the pencil - algebraic work needed!
           Last prime = 8543.

%3 = 2
gp > mpm1(67,,30,2700)

Factoring M67 ...
        Beginning First Stage P-1 of M67 ...
           Base     = 3
           B1 Limit = 30
           B2 Limit = 2700
        First Stage completed. No luck! Trying Stage 2 ...
           Last prime = 29.

        193707721 is a factor of M67 in Stage 2a.
           Last used pair = 2706 (=6*451) +/-1.
time = 6 ms.
%4 = 193707721
gp >