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.
What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?
time complexity;cryptography;integers;factoring
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).