mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-12-27, 12:20   #12
Neutron3529
 
Neutron3529's Avatar
 
Dec 2018
China

110112 Posts
Default

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.

Last fiddled with by Neutron3529 on 2018-12-27 at 12:28
Neutron3529 is offline   Reply With Quote
Old 2020-02-02, 21:19   #13
Greybeard
 
Feb 2020

28 Posts
Default What if Frank Cole Had Access to a Modern PC?

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.
Greybeard is offline   Reply With Quote
Old 2020-02-03, 01:06   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Greybeard View Post
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.

Last fiddled with by R.D. Silverman on 2020-02-03 at 01:07 Reason: addendum
R.D. Silverman is offline   Reply With Quote
Old 2020-02-03, 02:24   #15
Greybeard
 
Feb 2020

210 Posts
Default

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

Maybe beggars can be choosers.
Greybeard is offline   Reply With Quote
Old 2020-02-04, 16:46   #16
chris2be8
 
chris2be8's Avatar
 
Sep 2009

34×23 Posts
Default

Code:
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
chris2be8 is offline   Reply With Quote
Old 2020-02-05, 02:06   #17
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

206738 Posts
Default

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



Code:
gp > tf_420c_s(67)
M67 has a factor: 193707721
time = 234 ms.
%1 = 193707721
gp >
LaurV is offline   Reply With Quote
Old 2020-02-05, 05:59   #18
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·7·419 Posts
Default

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

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

Last fiddled with by CRGreathouse on 2020-02-05 at 06:00
CRGreathouse is offline   Reply With Quote
Old 2020-02-05, 08:33   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
If you're willing to put in several minutes into optimizing your runtime, you can shave off a few more milliseconds.

Code:
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.
R.D. Silverman is offline   Reply With Quote
Old 2020-02-05, 08:54   #20
axn
 
axn's Avatar
 
Jun 2003

466910 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I did say "a few milliseconds". But of course, no one listens.
Are you seriously salty at people for being curious?!
axn is offline   Reply With Quote
Old 2020-02-05, 08:58   #21
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by axn View Post
Are you seriously salty at people for being curious?!
Did I gore your ox, too?
R.D. Silverman is offline   Reply With Quote
Old 2020-02-05, 10:15   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100001101110112 Posts
Default

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:

Code:
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 >

Last fiddled with by LaurV on 2020-02-05 at 10:15
LaurV 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 00:57.

Tue Aug 11 00:57:03 UTC 2020 up 24 days, 20:43, 1 user, load averages: 2.69, 1.93, 1.61

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.