RSA Labs FAQ -- Q49: What are the Prospects for a Theoretical Factoring Breakthrough?

###

### Question 49. What are the Prospects for a Theoretical Factoring Breakthrough?

Factoring is widely believed to be a difficult mathematical problem, but it has not been proved so. Therefore, there remains a possibility that an easy factoring algorithm will be discovered. This development, which could seriously weaken RSA, would be highly surprising and the possibility is considered remote by the researchers most actively engaged in factoring research.

Another possibility is that someone will prove that factoring is difficult. Such a development, while unexpected at the current state of theoretical factoring research, would guarantee the security of RSA beyond a certain key size.

Even if no breakthroughs are discovered in factoring algorithms, both factoring and discrete logarithm problems can be solved efficiently on a quantum computer (see Question 109) if one is ever developed.