Search code examples
cryptographycomputer-science

Is the integer-factorization problem (used for many cryptographic applications) NP-Complete?

As the question states, does the integer-factorization problem fall into the class of NP-Complete problems?

Solution

  • Factoring:

    • It is not known to be NP-complete. (No reduction from an NP-complete problem has been found.)
    • It is not known not to be NP-complete either (if we knew the latter about some nontrivial problem in NP, it would mean P≠NP, so the latter is not surprising).
    • No polynomial factoring algorithm is known (or believed to exist), so it is believed not to be in P either.

    The informal consensus/belief is that this is one of the "in-between" problems that are not in P and are not NP-complete. Of course, this belief is less strong and widely held than P≠NP.