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.

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 3, 2014 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
    Commented Nov 3, 2014 at 8:24
  • $\begingroup$ @Raphael complexity of the problem $\endgroup$
    – John Demetriou
    Commented Nov 3, 2014 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
    Commented Nov 3, 2014 at 9:40

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Second largest factor is not helpful for factoring RSA private keys, because there should be two factors of rather similar size. A primality check for a 768 bit number is quite trivial. $\endgroup$
    – gnasher729
    Commented Jan 18, 2022 at 15:35
  • $\begingroup$ @gnasher729, factoring != checking for primailty. The latter is known to be in P, whereas no poly time algorithm is known for the prior. $\endgroup$
    – john_leo
    Commented Feb 25, 2022 at 11:03
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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