# What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

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.

• 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? Nov 3, 2014 at 8:19
• Are you asking for the complexity of the problem, or for the runtime of the brute force algorithm?
– Raphael
Nov 3, 2014 at 8:24
• @Raphael complexity of the problem Nov 3, 2014 at 8:35
• @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? Nov 3, 2014 at 9:40