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
    @Tony (didn't get pinged, eh.): He's $a$sking 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
    @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.