# How long does the General Number Field Sieve actually take?

According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer.

Using the complexity equation for the General Number Field Sieve with n=2^768 yielded 8.7*10^31 operations (calculated using Maxima). Let's naively assume a computer can perform 1 billion operations per second. Then that comes out to 2.73*10^13 years. That's off the reported value of 2.0*10^3 years by 10 orders of magnitude!

What am I missing? Calculations I did for other primes yielded similar over-estimates. Am I doing something wrong? Or is the complexity bound really just that loose?

• please, write your calculations from $8.7\cdot 10^{31}$ to $2.73\cdot 10^{13}$ Feb 27, 2016 at 20:24
• I'm not sure what you're asking; do you just want me to write the intermediate steps? Both calculations are essentially just plug and chug but if you think that would help I'll add them. Feb 27, 2016 at 20:44
• Intermediate steps) and is "your" biliion $10^9$ or $10^{12}$? Feb 27, 2016 at 20:48
• @Mr.Newman I did in fact mean $10^9$; a modern single-core computer can't possibly perform $10^{12}$ operations per second. Mar 20, 2016 at 7:36

There is an error in your "complexity equation". Replace the constant $\sqrt{\frac{64}{9}}$ by $\sqrt[3]{\frac{64}{9}}$. Wolfram Mathematica says, that if $N=2^{768}$, that $$\exp{\left(\sqrt[3]{\frac{64}{9}}(\ln N)^{1/3}(\ln \ln N)^{2/3}\right)}/10^{12}/3600/24/365=3.41\cdot 10^3$$

In view of Coppersmith's paper this constant can be $\frac{1}{3}(92+26\sqrt{13})^{1/3}=1.902$, with respect to some modifications of the method, and, so, result time is $1.9\cdot 10^3$.

• Actually I'm pretty sure that's just a different approximation. In my brief searches there is actually some debate about what exactly that constant should be. I have seen the equation with both the squareroot which is 2.667 and (1 plus the cuberoot) which is 2.923. In either case such a small difference should note result in 10 orders of magnitude error. Feb 27, 2016 at 20:42
• @TheSchwa: $\sqrt[3]{\frac{64}{9}}$ is correct. And it is $\sqrt[3]{\frac{64}{9}} + o(1)$, not $\sqrt[3]{\frac{64}{9}} + 1$. So Mr.Newman's answer is spot on. (Think about it: how could $\sqrt\frac{64}{9}$ not be a misprint?!) Feb 27, 2016 at 21:19
• Ah woops good point >.< Feb 28, 2016 at 3:14
• Although I'm still surprised changing the constant by 0.3 resulted in a difference of 8 orders of magnitude between answers; exponential growth not intuitive and etc. Thanks for pointing out the error :) Feb 28, 2016 at 3:21
• I just realized there's still a problem here; a 2.2GHz single core computer couldn't possibly do $10^{12}$ operations per second...according to wikipedia and it's Dell reference, we can estimate that the single-core 2.2GHz computer can perform $4*2.2*10^9 = 8.8$ GFLOPS, and so it's general performance must be somewhat less than that. Using $10^{12}$ gives millions of years instead of thousands. Thoughts? Mar 20, 2016 at 7:43

@TheSchwa, did you ever resolve your final comment about $$10^9$$ vs $$10^{12}$$?

In the paper published by the researchers who cracked RSA-768 they say:

Our computation required more than $$10^{20}$$ operations. With the equivalent of almost 2000 years of computing on a single core 2.2GHz AMD Opteron, on the order of $$2^{67}$$ instructions were carried out.

More precisely, it required $$1.4757 \times 10^{20}$$ operations (my calculation, just $$2^{67}$$). I'm speculating that to get their "almost 2000 years" they divided the number of operations ($$1.4757 \times 10^{20}$$) by the estimated FLOPs of the machine (sockets = 1, $$\times$$ cores = 1, $$\times$$ clock cycles = $$2.2 \times 10^9$$, $$\times$$ Ops/cycle = just over 1 (by implication)) which would give "almost" 2000 years of processing.