mersenneforum.org > Math How did Prof.Cole factor M67?
 Register FAQ Search Today's Posts Mark Forums Read

2020-02-03, 01:06   #14
R.D. Silverman

Nov 2003

22·5·373 Posts

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

Last fiddled with by R.D. Silverman on 2020-02-03 at 01:07 Reason: addendum

 2020-02-03, 02:24 #15 Greybeard   Feb 2020 210 Posts Wow! Thanks. That was sure fast enough, and spot on point. Maybe beggars can be choosers.
 2020-02-04, 16:46 #16 chris2be8     Sep 2009 34×23 Posts 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
 2020-02-05, 02:06 #17 LaurV Romulan Interpreter     Jun 2011 Thailand 206738 Posts 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 >
 2020-02-05, 05:59 #18 CRGreathouse     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 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
2020-02-05, 08:33   #19
R.D. Silverman

Nov 2003

746010 Posts

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

2020-02-05, 08:54   #20
axn

Jun 2003

466910 Posts

Quote:
 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?!

2020-02-05, 08:58   #21
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by axn Are you seriously salty at people for being curious?!
Did I gore your ox, too?

 2020-02-05, 10:15 #22 LaurV Romulan Interpreter     Jun 2011 Thailand 100001101110112 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 2 2016-11-03 17:00 lfm Data 15 2010-03-30 21:18 fivemack ElevenSmooth 4 2008-05-07 19:28 matt00926 Hardware 3 2005-03-16 00:15 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