cryptography - 整数分解问题(用于许多加密应用程序)是 NP-Complete 问题吗？

Question

正如问题所述，整数分解问题是否属于 NP 完全问题？

Answer 1

因数:

不知道是 NP 完全的。 (没有发现 NP 完全问题的减少。)

也不知道它不是 NP 完全的(如果我们知道后者关于 NP 中的一些非平凡问题，那就意味着 P≠NP，所以后者并不奇怪)。

没有多项式因式分解算法是已知的(或相信存在)，因此相信它也不在 P 中。

非正式的共识/信念是，这是不在 P 中且不是 NP 完全的“中间”问题之一。当然，这种信念不如 P≠NP 强烈和广泛。