2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ please, write your calculations from $8.7\cdot 10^{31}$ to $2.73\cdot 10^{13}$ $\endgroup$
    – Sergey Zaitsev
    Feb 27, 2016 at 20:24
  • $\begingroup$ 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. $\endgroup$
    – TheSchwa
    Feb 27, 2016 at 20:44
  • $\begingroup$ Intermediate steps) and is "your" biliion $10^9$ or $10^{12}$? $\endgroup$
    – Sergey Zaitsev
    Feb 27, 2016 at 20:48
  • $\begingroup$ @Mr.Newman I did in fact mean $10^9$; a modern single-core computer can't possibly perform $10^{12}$ operations per second. $\endgroup$
    – TheSchwa
    Mar 20, 2016 at 7:36

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – TheSchwa
    Feb 27, 2016 at 20:42
  • 4
    $\begingroup$ @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?!) $\endgroup$
    – TonyK
    Feb 27, 2016 at 21:19
  • $\begingroup$ Ah woops good point >.< $\endgroup$
    – TheSchwa
    Feb 28, 2016 at 3:14
  • $\begingroup$ 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 :) $\endgroup$
    – TheSchwa
    Feb 28, 2016 at 3:21
  • 1
    $\begingroup$ 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? $\endgroup$
    – TheSchwa
    Mar 20, 2016 at 7:43
1
$\begingroup$

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

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .