3
$\begingroup$

If one should attempt to factorize a number like the RSA-2048, or in general any number with $n$ decimal digits, using the best algorithm available and a modern desktop PC, what is the approximate length in time it would take (as a function of $n$) ? I'd like a general formula (possible parameterized with CPU speed and/or # of cpu's) so I can apply it to other numbers and PCs.

Thanks

  • 0
    Oh, you're ignoring the time it takes to read and write data (which is considerable if you've quite the pile of digits)? On computers nowadays, those might take more time than the arithmetic operations themselves...2011-07-16
  • 1
    You'll likely be shuttling data in between operations... unless you've big enough RAM, that is. Besides, the architecture of your box is another possible influence...2011-07-16
  • 0
    Talking about running time estimation (apart any input/output, memory usage consideration).2011-07-16
  • 0
    J.M., what are you talking about??2011-08-15
  • 0
    @Tony (didn't get pinged, eh.): He's asking about the time it'll take to factor. My point was that the non-arithmetic operations like moving data around can take more time than the factoring algorithm itself.2011-08-16

2 Answers 2

4

The number field sieve algorithm is generally the most efficient factoring algorithm and has a running time of $$O(\exp(c \sqrt[3]{(\log N)(\log \log N)^2}))$$ but I don't think it feasible or meaningful to derive a formula for the absolute time of computation.

  • 0
    Thank you. What could be an idea to transform the above concept in an actual time estimate, possibly by making assumption of the CPU power ? Just to have a rough idea. Are we talking of months, years, dozen of years, centuries, ... ?2011-07-16
  • 0
    @TauLee: You have the formula, just plug in $N$... For RSA-2048, I got $$152373858906444928985207904781622575.47$$2011-07-16
  • 0
    Very interesting François. So, to convert this number to an actual time estimate, could we, for instance, multiply for a constant (a time length) expressing the CPU speed. What could be a somehow meaningful constant ? Looks live that even if it were a few nanoseconds, we are talking here of a very long time.2011-07-16
  • 2
    @TaoLee: Exactly. That is why RSA encryption works.2011-07-16
  • 0
    I am wondering what was the point to post a "challenge" that even assuming 1 nanosecond (one billionth of a second) per integer (which seems by far unrealistic, is it ?) would still take about 4.831 Millions of Billions years to compute ?? (did i do that right?) And they had the courage to put a prize on it ? Not only... they also withdrew it... maybe were afraid someone could actually solve the challenge ;-) Vikipedia says "RSA-2048 may not be factorizable for many years to come" !! Are they supposed to be funny ?2011-07-16
  • 0
    @François G. Dorais, The age of the universe is estimated just 13.75 billion years http://en.wikipedia.org/wiki/Age_of_the_universe) and the sun 5 billion years (http://curious.astro.cornell.edu/question.php?number=389) and already half way. ??2011-07-17
  • 0
    @TaoLee: The number field sieve is only one step along the path of better and better factoring algorithms. It is conceivable that a clever new algoritm could factor RSA-2048 in a matter of days.2011-07-17
  • 0
    @François G. Dorais, you sound pretty sure about that ;-) Any special premonitions ? Are you seeing some possibilities or different avenues of attack ?2011-07-17
  • 0
    @Francois, I don't see how you "plug in $N$" and get a number when the formula has a big-oh and an unexplained constant $c$.2011-07-17
  • 0
    @Gerry Myerson, hmmm i guess we are back to the original question. Given a time complexity is some form O(F(n)), where n is the size of input, what is an "acceptable" way to attempt an estimate (even very approximate, just to have an idea - for VERY LARGE n) of actual time (using some param which express the cpu speed) ?2011-07-17
  • 0
    @Gerry: I used the formula from Wikipedia, which says that $c = (64/9)^{1/3} + o(1)$. I did ignore the $o(1)$, but all I wanted is to illustrate the fast growth of this function.2011-07-17
  • 0
    @Gerry Myerson, @François G. Dorais, well considering the constant (which worsen the situation, being about 2), we still have that even assuming 1 billionth of a second per integer, we still add up to a time which is Millions of times the lifetime of the universe ?? How can this be ? Is something wrong here ?2011-07-17
  • 0
    @TaoLee: Nothing is wrong there. The security of RSA depends on factoring being *incredibly* difficult to do. The publish a challenge to see if someone can find a general method to factor/break RSA in reasonable (polynomial) time. This is because the intractability of factoring is not known.2011-07-17
  • 0
    @Brandon Carter, @Gerry Myerson, @François G. Dorais, ok i see. But is it ever possible that we can go from Millions times the lifetime of the universe (something totally unimaginable) to just a few days of processing time, with some other (polynomial) algorithm ? It seems pretty far fetched ... Also i have another doubt. Assume, for instance, that some genius ever found such an algorithm (provided it can exist at all ??). Would it be safe for him/her to make public the discovery ? I can't imagine the gravity of consequencies on all planetary security ...2011-07-17
  • 2
    @TaoLee, we simply don't know what the true complexity of factorization is. Some of us are old enough to remember when factoring a 20-digit number was a great accomplishment. We have faster machines now, but just as important we have CFRAC and quadratic sieve and ECF and number field sieve and we just don't know whether something vastly better is just around the corner or whether we'vve gone about as far as we can go. If large-scale quantum computing becomes practical, then all bets are off. As for safety, you've been watching too many movies.2011-07-18
  • 0
    @Gerry Myerson, @Brandon Carter, @François G. Dorais, ahah maybe! Anyway he could "sell" the discovery to some company or service which would use it in secret, to clearly have an edge. Don't think this is too fictional ;-))) Anyway do you think is acceptable the computation i did multiplying the Running Time formula for a billionth of a second (just to have a very rough idea or the size of the phenomenon) or is it pure nonsense ?2011-07-18
3

As Brandon Carter said, the Number Field Sieve is the fastest known algorithm for factoring numbers that are at the limits of our capability. But it won't run on a modern desktop PC, because the matrix step at the end requires too much RAM. More precisely, for numbers that are small enough to factor on a PC using the Number Field Sieve, the Multiple Polynomial Quadratic Sieve is faster.

But in any case RSA-2048 is beyond reach. It's like interstellar travel: any program that you launch today to factor RSA-2048 will inevitably be beaten by a program using a better algorithm, discovered some time in the next 100 years.