为什么分解质因数属于NP问题，而不属于P问题？

Question

因式分解：给定整数N，找到两个小于N的正整数a和b（1 < a, b < N），使得它们的乘积等于N。如果这样的a和b不存在，那么N是一个质数。

我知道判断质数可以用P算法，但为什么不能用这种方法做因式分解呢？

这是我的算法：

For each a = 1 ... sqrt(N)
    if(N % a == 0)
        b = N/a
        add (a,b) to the result
    Endif
EndFor

这个运行时间为 O(sqrt(N))。

- Nayana

---

输入的大小是表示它所需的位数，而不是输入的值。 - Mankarse

义务维基百科参考链接 - Geobits

如果你真的想知道为什么密码学有效，以及像RSA这样的东西为什么很难破解，那么你忽略了它是一个模数分解的事实。 - Leeor

多项式时间素性测试算法与此算法完全不同，顺便说一下。 - Teepeemm

@phoeagon 如果在SO上发布了一个6行代码解决P vs NP问题，那不是太神奇了吗？ - Hank Igoe

Answer 1

单个数字的输入大小是通过其二进制表示的长度来衡量的。准确地说，输入数值n的大小与log_2(n)成比例。因此，您的算法运行时间为指数级。

例如，假设我们正在使用您的算法分解一个数字N。如果N是质数，则您至少需要测试sqrt(N)个因子。(或者您可以为此计算一个素数表，但仍然不是线性的)。

无论如何，您会进行sqrt(N)次测试。但问题的规模定义为S=log2(N)。所以我们有N=2^S。因此它是一个sqrt(2^S)=2^(S/2)，这是指数级的。

- phoeagon

---

很抱歉，我仍然不明白为什么它是指数时间。所以，对于输入大小N，实际上是2^N，你的意思是这样吗？ - Nayana

@Nayana 该算法的运行时间为O(sqrt(2^n))，约等于O(1.414^n)，其中n是存储输入数字N所需的位数（即n = log2(N)）。 - interjay

@interjay 好的，我明白了！输入大小非常小，因此与问题规模相比，看似正常的时间也变成了指数级别的 :) - Abhishek Bansal

@phoeagon，我认为Abhishek Bansal之前说的也有点道理。比如我们传递一个数组并尝试在其中找到特定的数字。问题的运行显然是O(N)，但问题的大小再次是S=log2(N)，因为它是由其二进制表示的长度来衡量的？这种解释使得每个多项式时间算法都成为指数级... - Nayana

@Nayana 或者试着这样想。一个只有单个数字值作为输入的问题很可能是数学问题，因此预计需要处理巨大的数字。此外，如果考虑到小于 V 的值数组的 O(logV) 部分，则必须进行替换。O(NlogN) 的反函数并不简单，可能会引起混淆。此外，在 N 和 NlogN 之间确实存在很小的差异，但在 1、logN 和 N 之间却不是这样。 - phoeagon