1
$\begingroup$

I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well.

I also know that is it somewhat exponential or even more and with current machines it is rendered impossible to do in less than a year to find it for numbers used in an RSA protocol (they are too big).

What I am asking is what is the actual complexity of such a task? I am looking for average and maximum complexity.

$\endgroup$
  • 1
    $\begingroup$ It's a bit unclear what exactly you're asking for. Are you asking for the composite numbers used in the RSA algorithm (ie composites that are consist of two prime numbers exactly), or general composite numbers? Also are you asking for the complexity using try-and-error, or the state-of-the-art algorithms? $\endgroup$ – john_leo Nov 3 '14 at 8:19
  • 1
    $\begingroup$ Are you asking for the complexity of the problem, or for the runtime of the brute force algorithm? $\endgroup$ – Raphael Nov 3 '14 at 8:24
  • $\begingroup$ @Raphael complexity of the problem $\endgroup$ – John Demetriou Nov 3 '14 at 8:35
  • $\begingroup$ @john_leo I am asking for composite numbers used in RSA protocol and the complexity it takes to solve such a task.As for the algorithm used I do not know, the "best" algorithm? $\endgroup$ – John Demetriou Nov 3 '14 at 9:40
4
$\begingroup$

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. You can find the heuristic runtime in the linked Wikipedia-article.
Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. Thus every now and then it's faster.
The largest "RSA"-number yet factored is a 768 bit number (RSA Factoring Challenge).

$\endgroup$
3
$\begingroup$

The computational complexity of factorization is one of the biggest open problems in computer science. There's a summary of what's known on Wikipedia; the summary of the summary is that it's known to be in both NP and co-NP so it's unlikely to be NP-complete, or the polynomial hierarchy collapses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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