20181227, 12:20  #12 
Dec 2018
China
11011_{2} Posts 
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^671. It could not be humanfriendly to reproduce such step, here I will give some example using Pari/GP: > n=2^671 > 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^671, p2^671 ,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 20181227 at 12:28 
20200202, 21:19  #13 
Feb 2020
2_{8} Posts 
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 21digit 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 highend 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 wildandillspentyouth (which in my case, is pretty much all one word), I haven't used any higher math in decades, so please try not to overassume 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. 
20200203, 01:06  #14  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Cole did it via Fermat's method with exclusion moduli. Last fiddled with by R.D. Silverman on 20200203 at 01:07 Reason: addendum 

20200203, 02:24  #15 
Feb 2020
2_{10} Posts 
Wow! Thanks. That was sure fast enough, and spot on point.
Maybe beggars can be choosers. 
20200204, 16:46  #16 
Sep 2009
3^{4}×23 Posts 
Code:
chris@rigel:~/bin$ time yafu 'siqs(2^671)' ***factors found*** P12 = 761838257287 P9 = 193707721 ans = 1 real 0m0.135s user 0m0.088s sys 0m0.028s Chris 
20200205, 02:06  #17 
Romulan Interpreter
Jun 2011
Thailand
20673_{8} Posts 
Pari, Trial Factoring with 420 classes (script posted here in the past), slow/moderate laptop (i53340M at 2.7GHz)
Code:
gp > tf_420c_s(67) M67 has a factor: 193707721 time = 234 ms. %1 = 193707721 gp > 
20200205, 05:59  #18 
Aug 2006
2·7·419 Posts 
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 Last fiddled with by CRGreathouse on 20200205 at 06:00 
20200205, 08:33  #19  
Nov 2003
7460_{10} Posts 
Quote:
I did say "a few milliseconds". But of course, no one listens. 

20200205, 08:54  #20 
Jun 2003
4669_{10} Posts 

20200205, 08:58  #21 
Nov 2003
1D24_{16} Posts 

20200205, 10:15  #22 
Romulan Interpreter
Jun 2011
Thailand
10000110111011_{2} Posts 
Our goal was not to get the fastest factoring method, but to show that even such nonefficient 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 P1 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 P1 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 20200205 at 10:15 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Got an email from prof. Keller  ET_  FermatSearch  2  20161103 17:00 
big factor  lfm  Data  15  20100330 21:18 
New factor  fivemack  ElevenSmooth  4  20080507 19:28 
Prime 95 + BSOD issues Win xp Prof sp2  matt00926  Hardware  3  20050316 00:15 
Shortest time to complete a 2^67 trial factor (no factor)  dsouza123  Software  12  20030821 18:38 