是整数因子分解问题(用于许多加密应用程序)NP-Complete?

Gai*_*ail 4 computer-science cryptography

正如问题所述,整数因子分解问题是否属于NP-Complete问题?

Shr*_*saR 9

保理:

  • 不知道它是NP完全的.(没有发现NP完全问题的减少.)
  • 不知道不是 NP完全(如果我们知道后者关于NP中的一些非平凡问题,则意味着P≠NP,因此后者并不令人惊讶).
  • 没有多项式因子分解算法是已知的(或者认为存在),因此认为它也不在P中.

非正式的共识/信念是,这是"中间"问题之一,不在P中并且不是NP完全的.当然,这种信念不如P≠NP那么强大和广泛存在.