Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 384
Gail Avatar asked Jan 23 '23 06:01

Gail


1 Answers

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.

like image 59
ShreevatsaR Avatar answered Jan 24 '23 18:01

ShreevatsaR