整数分解为什么是非多项式时间？

Question

我只是计算机科学的初学者。我了解了一些有关运行时间的知识，但我不能确定我理解的是否正确。所以请帮助我。

因此，整数因数分解目前不是一个多项式时间问题，但素性测试是一个多项式时间问题。假设要检查的数字是n。如果我们运行一个程序，仅判断从1到sqrt(n)的每个数字是否能够被n整除，并且如果答案是肯定的，则存储该数字。我认为这个程序是多项式时间的，对吗？

我可能错误的一个可能原因是，因子分解程序应该找到所有质数，而不是发现的第一个质数。所以也许这就是原因。

然而，在公钥加密中，找到大数的质因子是攻击加密的关键。由于通常大数字（公钥）只是两个质数的乘积，找到其中一个质数意味着找到另一个质数。这应该是多项式时间的。那么为什么很难或不可能攻击呢？

- zyl1024

---

你最开始说的是检查一个数字是否为质数。 - Emil

因为这些数字非常庞大！ - nullpotent

如果你相信算法X具有多项式复杂度，请尝试编写表达其复杂度的多项式。如果成功了，那么X就具有多项式复杂度；如果失败了，你可能会安慰自己认为X没有多项式复杂度，这比你没能找到（或者说是一个）多项式更令人欣慰。但是，更严肃地说，尝试编写一个关于整数因子分解复杂度的方程，以整数位数为变量，并研究其形式。 - High Performance Mark

Answer 1

对于像“多项式因式分解算法”这样的复杂度的非正式描述通常是指相对于输入的大小，而不是输入的解释。因此，当人们说“没有已知的多项式因式分解算法”时，他们的意思是没有已知的算法能够在相对于N的时间内以多项式时间运行来因式分解N位自然数。不是相对于该数字本身的多项式，它可能高达2^N。

- Ryan Culpepper

---

输入的大小不就是输入的解释吗？为什么我们要使用位来表示输入的大小而不是输入的解释？ - Gerald

Answer 2

困难的因式分解是一种美妙的数学问题，易于理解，并立即将您带到人类知识的边缘。总结一下（今天）该主题的知识：我们不知道为什么它很难，没有任何证明，而且我们拥有的最佳方法运行时间超过多项式时间（但也显著少于指数时间）。素性测试在P中的结果是相当新的；请参阅链接的维基百科页面。

我所知道的关于难度的最好的启发式解释是质数是随机分布的。其中一个更容易理解的结果是狄利克雷定理。这个定理说每个算术级数都包含无限多个质数，换句话说，您可以认为质数在进展方面是密集的，这意味着您无法避免遇到它们。这是一个相当大的这类结果中最简单的一个；在所有这些结果中，质数以非常类似于随机数的方式出现。

事实分解的困难程度类似于无法翻转一次性密码本。在一次性密码本中，有一个我们不知道的比特与另一个我们也不知道的比特进行异或运算。我们无法从已知XOR结果的单个比特中获取任何信息。将“比特”替换为“质数”，并将乘法替换为XOR，则得到了因数分解问题。就好像你将两个随机数相乘，而从乘积中获得的信息非常少（而不是零信息）。

- eh9

Answer 3

如果我们运行一个程序，仅仅是为了判断从1到sqrt(n)的每个数字是否能够整除n，如果答案是肯定的，那么就存储这个数字。

即使忽略可除性测试对于更大的数字需要更长时间这一点，如果你只是给n添加一个单独的（二进制）数字，这种方法所需的时间几乎会增加一倍。（实际上，如果你添加两个数字，它将需要两倍的时间）

我认为这就是指数级运行时间的定义：让n变长一位，算法所需的时间就会增加一倍。

但请注意，这个观察结果仅适用于您提出的算法。目前还不知道整数分解是否是多项式的。密码学家们确信它不是，但也有其他不依赖于质因数分解困难的替代算法（如椭圆曲线加密），以防万一...

- Thilo