Estimating time needed for GNFS

[CRGreathouse]

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?

[debrouxl]

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.

[CRGreathouse]

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.

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?

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?

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).

[jasonp]

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.

[CRGreathouse]

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?

[VBCurtis]

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.

[kracker]

If you need any benchmarks, I have a Haswell 4670k available.

[swellman]

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.

[frmky]

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.

+----------------+------------+----------+-----------+-------------+------------+
| 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  |
+----------------+------------+----------+-----------+-------------+------------+

[pinhodecarlos]

NFS@Home post-processing logs. All SNFS.

[pinhodecarlos]

Excel sheet.