What would be the scenario if P = NP for RSA algorithm?

Question

Suppose I am using RSA for my security system. Now someone discovers find a polynomial time algorithm for RSA. Then what measure should one that such that RSA never breaks. Maybe large number of used bits or something else.

Answer 1

If it is proven that P=NP then this means that a polynomial time algorithm for breaking RSA exists. Finding that algorithm might be challenging, though. On the other hand, P could be distinct from NP and yet factoring could accept a polynomial-time algorithm. Integer factorization is not proven to be a NP-complete problem.

Moreover, "polynomial" is an asymptotic behaviour, which describes how the running time of an algorithm behaves on sufficiently large inputs. Nothing says that common RSA key sizes are "sufficiently large" for the asymptotic behaviour to be a reasonably accurate estimate of performance on these key sizes. Finally, "polynomial" does not necessarily mean "fast"; an algorithm with cost O(n¹²) (for a RSA modulus of n bits) would have cost 2¹²⁰ for a 1024-bit RSA key, i.e. totally unachievable in practice.

That's the problem with reasoning on poorly-defined hypothetical scenarios: anything can happen, really. So the question cannot be answered, except by gut feelings. My own guts tell me that if a polynomial factorization algorithm is found, then it will probably be quite expensive for "normal" integer sizes, and use sufficiently advanced mathematics that we will have a few months or years before practical implementations appear, which should give use enough time to switch to something else (e.g. elliptic curves). But, of course, my guts are just digestive organs, good at breaking down food into nutriments; what do they really know about cryptography ?