Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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... –  J. M. Jul 16 '11 at 15:58
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... –  J. M. Jul 16 '11 at 16:07
    
Talking about running time estimation (apart any input/output, memory usage consideration). –  TaoLee Jul 16 '11 at 16:28
    
J.M., what are you talking about?? –  TonyK Aug 15 '11 at 19:48
    
@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. –  J. M. Aug 16 '11 at 3:53

2 Answers 2

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.

share|improve this answer
    
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, ... ? –  TaoLee Jul 16 '11 at 19:23
    
@TauLee: You have the formula, just plug in $N$... For RSA-2048, I got $$152373858906444928985207904781622575.47$$ –  François G. Dorais Jul 16 '11 at 20:28
    
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. –  TaoLee Jul 16 '11 at 21:43
2  
@TaoLee: Exactly. That is why RSA encryption works. –  El'endia Starman Jul 16 '11 at 22:01
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. –  Gerry Myerson Jul 18 '11 at 1:02

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.