mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-03-02, 04:17   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default 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?
CRGreathouse is offline   Reply With Quote
Old 2014-03-02, 07:46   #2
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

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.
debrouxl is offline   Reply With Quote
Old 2014-03-02, 15:29   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16E416 Posts
Default

Quote:
Originally Posted by debrouxl View Post
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 View Post
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 View Post
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 View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2014-03-02, 16:03   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×587 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
jasonp is offline   Reply With Quote
Old 2014-03-02, 17:01   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

586010 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2014-03-02, 22:16   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

52×167 Posts
Default

Laptop i7-quad (2600QM) @ 1.7Ghz (underclocked for heat management):
GNFS 108 took 0.6 thread-hours to poly select, 10 thread-hours to sieve, 1 thread-hour for matrix.
GNFS 116 took 2 GPU-hours to poly select, 42 thread-hours sieving, 2 thread-hours matrix.
GNFS 133 took 18 GPU-hours poly select, 230 thread-hours to sieve, 17 thread-hours for matrix.
GNFS 147 took 2 GPU-days poly select, 52 thread-days to sieve, 4 thread-days for matrix.

The CPU had 8 threads running during all sieving phases; 4 on GGNFS, 4 on ECM or other tasks. Linear Algebra had 2 threads on msieve, 2 on ECM or other light tasks. Hyperthreaded sieving is about 2/3rds the speed per thread of one thread per core work, so 30% faster overall vs HT disabled. In other words, each thread gets about 1.1 Ghz worth of speed, but 8 * 1.1 > 4 * 1.7.

Core2Quad @ 3.2Ghz, no HT:
GNFS 139 took 24 GPU-hrs poly select, 224 core-hours sieving, 38 core-hours matrix. 3 threads for sieve & matrix. 3 threads is too many for a Core2-generation CPU for linalg- see next entry.

GNFS 143 took 24? GPU-hrs poly select, 356 core-hours sieving, 20 hours matrix. Sieve was 2 threads, matrix single-threaded.

Sievers are windows 64-bit. Msieve versions varied over time, but most of these were before the recent 25% matrix speedup.

Last fiddled with by VBCurtis on 2014-03-02 at 22:24 Reason: i7 model number, sieve version
VBCurtis is offline   Reply With Quote
Old 2014-03-02, 22:58   #7
kracker
ἀβουλία
 
kracker's Avatar
 
"Mr. Meeseeks"
Jan 2012
California, USA

2·13·83 Posts
Default

If you need any benchmarks, I have a Haswell 4670k available.
kracker is offline   Reply With Quote
Old 2014-03-03, 23:13   #8
swellman
 
swellman's Avatar
 
Jun 2012

33×103 Posts
Default

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.
swellman is offline   Reply With Quote
Old 2014-03-03, 23:23   #9
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

43×47 Posts
Default

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
frmky is offline   Reply With Quote
Old 2014-03-05, 00:02   #10
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

33×132 Posts
Default

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

Last fiddled with by pinhodecarlos on 2014-03-05 at 00:02
pinhodecarlos is offline   Reply With Quote
Old 2014-03-05, 00:06   #11
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

33×132 Posts
Default

Excel sheet.
Attached Files
File Type: zip SNFS and GNFS.zip (15.9 KB, 59 views)
pinhodecarlos is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Estimating time needed for GNFS CRGreathouse Factoring 0 2014-03-02 04:18
Predicting the needed time for high n-values? Rincewind Sierpinski/Riesel Base 5 4 2009-06-11 12:24
GNFS poly search time limit oddity Andi47 Msieve 13 2009-02-25 12:33
Discussion about CPU time needed and k's remaining Siemelink Conjectures 'R Us 41 2008-07-11 23:05
Running time for GNFS koders333 Factoring 4 2006-02-27 14:33

All times are UTC. The time now is 08:18.

Thu May 28 08:18:51 UTC 2020 up 64 days, 5:51, 1 user, load averages: 1.52, 1.81, 1.89

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.