I've heard differing opinions/statements of fact from different professors and sources as to whether cracking RSA is "thought" to be in NP, or known to be an NP-complete problem. Can anyone shed light on this discrepancy? which is it, or do we know?

  • 4
    $\begingroup$ This question is not research level. Read wiki Integer factorization difficulty and complexity. $\endgroup$ Aug 16, 2011 at 2:20
  • 4
    $\begingroup$ George Bush: Great president, or greatest president? $\endgroup$
    – Aaron Roth
    Aug 16, 2011 at 2:57
  • $\begingroup$ Please read the FAQ to understand the scope of cstheory. I am closing the question as off-topic and migrating to Math.SE. $\endgroup$
    – Kaveh
    Aug 16, 2011 at 5:02

1 Answer 1


Proving that breaking any cryptosystem is $\mathsf{NP}$-complete would be a great achievement in cryptography, since $\mathsf{P} \neq \mathsf{NP}$ is probably the most "standard" hardness assumption around. For the case of RSA, security of the system is based on hardness of the integer factorization problem. This problem lies in the intersection of $\mathsf{NP}$ and $\mathsf{coNP}$, and is thus unlikely to be $\mathsf{NP}$-complete. However, it's obviously in $\mathsf{NP}$ (just guess the private key, and decrypt).

  • 9
    $\begingroup$ iirc then cracking RSA is not even known to be equivalent to factoring. It could be the case that factoring is hard, but cracking RSA is easy. $\endgroup$ Aug 16, 2011 at 3:07
  • 1
    $\begingroup$ There have been a number of non-number-theoretical attempts on NP-complete cryptosystems too (for instance, systems based on the knapsack problem), but all of those have had specialized constructions that turn out to yield non-NP-complete versions of the appropriate problem. In fact, proving the secureness of an encryption scheme (more specifically, proving the existence of one-way functions) is even harder than proving the P-NP separation, since IIRC there are worlds where P is inequal to NP but one-way functions don't exist. $\endgroup$ Aug 16, 2011 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .