If you want to make money online : Register now

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

, , No Comments
Problem Detail: 

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.

Asked By : John Demetriou

Answered By : john_leo

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32633

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback