Edge of factoring technology?

Please consult Wikipedia before posting a question. You can still ask about the Wikipedia article, of course.

See Integer factorization: Current state of the art.


The same algorithm is used for factoring, the Number-Field Sieve. It's probably been optimized further. But the main difference between now and then is computing power. Since the asymptotic running-time of the NFS is "known", you can even extrapolate into the future (assuming your favorite version of Moore's law).


For factoring RSA moduli (product of two large distinct primes), the Number Field Sieve is still king. It has two phases: a parallelizable sieving phase where we look for polynomials, then a non-parallelizable matrix reduction step that is usually done on a large computer.

If quantum computers ever become practical, they can factor integers via Shor's algorithm in polynomial time. In fact, this is the only known compelling application for them, but it's enough for the military to spend millions in the U.S. funding research on quantum computers.

Note: Peter Shor is a frequent contributor on this site.


Well understanding, that your question targets the factorization problem: Guess the effective strength of public key cryptography lies in the method, i.e. that you can establish private sessions without preexisting secret. E.g. you could use a transient public key with ´sufficient´ length to exchange a secondary set of keys, which even the public key of is only known to your counterpart. So nobody else knows about a secondary modulus and there is no factorization problem, at all, as the ´man in the middle´ will see nothing but a stream of white noise.