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.

  • 2
    Partial duplicate of How will security need to be changed if P=NP?
    – Polynomial
    Nov 5, 2012 at 14:57
  • Depends on the exact performance characteristics of that hypothetical algorithm. Polynomial can be anything from O(n) to O(n^1000). So this question is unanswerable. Nov 5, 2012 at 14:59
  • 1
    @Polynomial No, I don't think this question is a duplicate. It's more specific, and calls for more specific answers. Nov 5, 2012 at 16:23

1 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(n12) (for a RSA modulus of n bits) would have cost 2120 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 ?

  • 2
    Bowel-based crypto needs more study. I propose a new field: Gastrocryptography
    – Polynomial
    Nov 5, 2012 at 15:49
  • 1
    MMM. Sounds yummy. I'll bring the S-boxes.
    – tylerl
    Nov 6, 2012 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.