mersenneforum.org Estimating time needed for GNFS
 Register FAQ Search Today's Posts Mark Forums Read

 2014-03-02, 04:17 #1 CRGreathouse     Aug 2006 32×5×7×19 Posts Estimating time needed for GNFS I've written a page for my website which estimates, for a given number of digits and processor, how long it would take to run GNFS on that number. This is intended as a resource for people entirely unfamiliar with practical factorization, not for the experts here who will have well-honed intuition. Still, even with that relatively low goal, I'd like to tweak my tool before posting it before the world. Here is my simple-minded methodology: Get data on how long existing GNFS efforts took Interpolate with the usual L[1/3] between existing efforts Scale (linearly!) based on the Passmark score for processors For the first point, I took the 6 data points from GNFS Factoring Statistics of RSA-100, 110, ..., 150. This means a Pentium 4 taking 15 hours for a C100, 53 hours for a C110, 219 hours for a C120, 643 hours for a C130, 1868 hours for a C140, and 5721 hours for a C150. Any ideas on how I could do this better?
 2014-03-02, 07:46 #2 debrouxl     Sep 2009 11110100012 Posts The two first points of your methodology are probably reasonable, but I wonder whether generic benchmarks are a reliable base for scaling ? IOW, I wonder whether they test the exact combination of operations used for NFS, and how well they account for micro-architecture and memory bandwidth variations which affect NFS run time. Having started integer factoring in 2009, I'm unfit for commenting on the 15 hours figure for a C100 on a P4. On 2011-2013 computers, such numbers take much less time, that's for sure Other data points: * in 2009, factoring a 512-bit RSA key took an estimated 73 wall clock days on a then-old dual-core Athlon 64 (Benjamin Moody, triggering the "TI signing key controversy"); * in 2013, sieving another 512-bit RSA key took 3-4 wall clock days on up to 42 cores of varying power, followed by less than 24 wall clock hours of post-processing on 4 threads. 512-bit RSA keys (GNFS 154-155) are about twice harder than GNFS 150 tasks.
2014-03-02, 15:29   #3
CRGreathouse

Aug 2006

32·5·7·19 Posts

Quote:
 Originally Posted by debrouxl I wonder whether generic benchmarks are a reliable base for scaling ? IOW, I wonder whether they test the exact combination of operations used for NFS, and how well they account for micro-architecture and memory bandwidth variations which affect NFS run time.
I imagine they work reasonably within a processor family but poorly outside that. Since I'm talking about several generations of processors, I can't even guess if it's in the right ballpark. I've never been able to get GGNFS working properly on my system so I don't have numbers.

Quote:
 Originally Posted by debrouxl Having started integer factoring in 2009, I'm unfit for commenting on the 15 hours figure for a C100 on a P4. On 2011-2013 computers, such numbers take much less time, that's for sure
Do you have any personal numbers to share?

Quote:
 Originally Posted by debrouxl in 2009, factoring a 512-bit RSA key took an estimated 73 wall clock days on a then-old dual-core Athlon 64 (Benjamin Moody, triggering the "TI signing key controversy")
My calculator extrapolates that this should have taken "4.0 months" on such a machine. Did 'for-the-masses' GNFS technology improve between 2004 and 2009?

Quote:
 Originally Posted by debrouxl in 2013, sieving another 512-bit RSA key took 3-4 wall clock days on up to 42 cores of varying power, followed by less than 24 wall clock hours of post-processing on 4 threads.
It's hard to say much about this without knowing the types of machines used (or exact time). Call it 151 core-days, making the average core just as powerful as Moody's (but faster by having more).

2014-03-02, 16:03   #4
jasonp
Tribal Bullet

Oct 2004

353810 Posts

Quote:
 Originally Posted by CRGreathouse My calculator extrapolates that this should have taken "4.0 months" on such a machine. Did 'for-the-masses' GNFS technology improve between 2004 and 2009?
Postprocessing using Msieve became feasible for the 512-bit size in late 2007. I think that using strictly the GGNFS tools, only one person managed a 512-bit factorization in 2006, and IIRC needed weeks on about 15 P3 processors for the sieving. The postprocessing for that job was slightly over the limit of what the GGNFS tools could handle. Since then, the sieving tools have gone through one revision by their author which made them much faster on 64-bit systems, but IIRC that was after 2009. So the improvement in runtime of the sieving phase primarily has Moore's law to thank.

Also, Kleinjung's announcement of improvements to GNFS polynomial selection in late 2008 made the sieving phase meaningfully faster, though it would be less than a factor of two.

Edit: I believe the Aoki et. al. paper reported results using their own lattice siever, whereas all the results we see here use variants of the Franke/Kleinjung siever. That could explain the difference too; the siever we use incorporates cache management techniques that had not been reported in 2004.

Last fiddled with by jasonp on 2014-03-02 at 16:05

 2014-03-02, 17:01 #5 CRGreathouse     Aug 2006 32×5×7×19 Posts Great. So if I understand correctly, it sounds like the processor scaling seems decent enough but that all times should be reduced by a factor of ~2 because of sieving and postprocessing improvements. (Thanks for your part in that, by the way!) To test the extrapolation I looked at RSA-768. They report 1500 core-years of Opterons at 2.2 GHz, which should be 375 processor-years on quad-core Opterons. My calculator reports 632.5 years, which is also close to the ~2 scaling you suggest for modern factorizations. (One wrinkle: they oversieved by a factor of 2, so perhaps this means they are actually 4 times faster rather than 2. But I'll leave this as-is since such oversieving might still be needed.) Does anyone have some recent (last few years) timings on GNFS attempts I can use for calibration? Last fiddled with by CRGreathouse on 2014-03-02 at 17:02
 2014-03-02, 22:58 #7 kracker     "Mr. Meeseeks" Jan 2012 California, USA 32×241 Posts If you need any benchmarks, I have a Haswell 4670k available.
 2014-03-03, 23:13 #8 swellman     Jun 2012 23·3·53 Posts Have you looked here? http://homepage2.nifty.com/m_kamada/math/graphs.htm I've got some personal data I will PM you tomorrow as well.
 2014-03-03, 23:23 #9 frmky     Jul 2003 So Cal 32·233 Posts It isn't too hard to extract meaningful data from NFS@Home. The time required for workunits doesn't vary too much for a given processor, so time based on the sieving range alone should be reasonably accurate. Edit: See if this makes sense. These are the numbers with the e value in the poly file, and the sieve range is (q_end - q_start)/10^6. Code: +----------------+------------+----------+-----------+-------------+------------+ | name | difficulty | q_start | q_end | sieve_range | e_value | +----------------+------------+----------+-----------+-------------+------------+ | 2_1584P | 168 | 45000000 | 305000000 | 260.0000 | 4.936e-13 | | C162_126_83 | 162 | 20000000 | 140000000 | 120.0000 | 1.127e-12 | | F2451 | 166 | 20000000 | 120000000 | 100.0000 | 6.331e-13 | | F1953 | 166 | 20000000 | 130000000 | 110.0000 | 5.640e-13 | | F1595 | 166 | 20000000 | 120000000 | 100.0000 | 5.919e-13 | | L1354 | 163 | 20000000 | 115376000 | 95.3760 | 9.339e-13 | | L1694 | 163 | 20000000 | 96000000 | 76.0000 | 9.137e-13 | | L1911 | 167 | 20000000 | 120000000 | 100.0000 | 5.513e-13 | | L2910 | 168 | 20000000 | 150000000 | 130.0000 | 3.942e-13 | | L3335B | 164 | 20000000 | 100000000 | 80.0000 | 7.898e-13 | | L3945A | 166 | 20000000 | 120000000 | 100.0000 | 5.890e-13 | | L2975B | 167 | 20000000 | 140000000 | 120.0000 | 5.068e-13 | | C155_3408_1311 | 155 | 26000000 | 100000000 | 74.0000 | 3.230e-012 | | C162_3408_1361 | 162 | 20000000 | 140000000 | 120.0000 | 1.164e-012 | | C166_4788_5159 | 166 | 40000000 | 264000000 | 224.0000 | 5.314e-013 | | C168_127_110 | 168 | 40000000 | 250000000 | 210.0000 | 4.765e-013 | | C168_130_119 | 168 | 40000000 | 274000000 | 234.0000 | 5.320e-013 | | C161_4788_5193 | 161 | 32000000 | 126000000 | 94.0000 | 1.406e-012 | | C158_3366_2103 | 158 | 20000000 | 120000000 | 100.0000 | 1.950e-012 | | C160_3408_1385 | 160 | 20000000 | 158000000 | 138.0000 | 1.333e-012 | +----------------+------------+----------+-----------+-------------+------------+ +----------------+------------+----------+-----------+-------------+------------+ | name | difficulty | q_start | q_end | sieve_range | e_value | +----------------+------------+----------+-----------+-------------+------------+ | G3p725 | 179.4 | 20000000 | 150000000 | 130.0000 | 1.047e-13 | | C176_3270_677 | 176 | 15000000 | 160000000 | 145.0000 | 1.321e-013 | | C178_3270_687 | 178 | 20000000 | 300000000 | 280.0000 | 9.700e-14 | +----------------+------------+----------+-----------+-------------+------------+ Last fiddled with by frmky on 2014-03-03 at 23:59
2014-03-05, 00:02   #10
pinhodecarlos

"Carlos Pinho"
Oct 2011
Milton Keynes, UK

494010 Posts

NFS@Home post-processing logs. All SNFS.
Attached Files
 done.zip (463.7 KB, 109 views)

Last fiddled with by pinhodecarlos on 2014-03-05 at 00:02

2014-03-05, 00:06   #11
pinhodecarlos

"Carlos Pinho"
Oct 2011
Milton Keynes, UK

22·5·13·19 Posts

Excel sheet.
Attached Files
 SNFS and GNFS.zip (15.9 KB, 115 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Factoring 0 2014-03-02 04:18 Rincewind Sierpinski/Riesel Base 5 4 2009-06-11 12:24 Andi47 Msieve 13 2009-02-25 12:33 Siemelink Conjectures 'R Us 41 2008-07-11 23:05 koders333 Factoring 4 2006-02-27 14:33

All times are UTC. The time now is 00:31.

Tue May 18 00:31:12 UTC 2021 up 39 days, 19:12, 0 users, load averages: 2.49, 2.30, 2.27