我只是计算机科学的初学者。我学到了一些关于运行时间的知识，但我不能确定我的理解是正确的。所以请帮助我。
所以整数分解目前不是多项式时间问题，而是素性检验。假设要检查的数字是n。如果我们运行一个程序只是为了确定从 1 到 sqrt(n) 的每个数字是否可以整除 n，如果答案是肯定的，则存储该数字。我认为这个程序是多项式时间，不是吗？
我错的一种可能方法是分解程序应该找到所有素数，而不是发现的第一个素数。所以也许这就是原因。
然而，在公钥密码学中，找到一个大数的素因数对于攻击密码学至关重要。由于通常一个大数（公钥）只是两个素数的乘积，所以找到一个素数就意味着找到另一个素数。这应该是多项式时间。那么为什么攻击很难或不可能呢？
诸如“多项式因式分解算法”之类的复杂性的随意描述通常是指相对于输入大小的复杂性，而不是对输入的解释。因此，当人们说“没有已知的多项式因式分解算法”时，他们的意思是没有已知的算法可以分解N位自然数，该算法在时间多项式中运行关于N。不是关于数字本身的多项式，最多可以是 2^ N。
因式分解的难度是那些简单易懂的美丽数学问题之一，可以立即将您带到人类知识的边缘。总结（今天）关于这个主题的知识：我们不知道为什么它很难，没有任何程度的证明，以及我们在超过多项式时间（但也明显少于指数时间）中运行的最佳方法。素数测试甚至在 P 中的结果是最近的；请参阅链接的维基百科页面。
我所知道的最好的启发式解释是素数是随机分布的。更容易理解的结果之一是狄利克雷定理。这个定理说每个算术级数都包含无限多个素数，换句话说，你可以认为素数相对于级数是密集的，这意味着你无法避免遇到它们。这是相当大的此类结果集合中最简单的一个；在所有这些中，素数的出现方式非常类似于随机数。
因此，因式分解的困难类似于无法逆转一次性填充。在一次性垫中，有一点我们不知道与另一个我们不知道的异或。知道 XOR 的结果，我们得到关于单个位的零信息。将“bit”替换为“prime”，将乘法替换为 XOR，就会出现因式分解问题。就好像您将两个随机数相乘，并且您从产品中获得的信息非常少（而不是零信息）。
如果我们运行一个程序只是为了确定从 1 到 sqrt(n) 的每个数字是否可以整除 n，如果答案是肯定的，则存储该数字。
即使忽略较大数字的可分性测试将花费更长的时间，如果您仅将单个（二进制）数字添加到n. （实际上如果添加两个数字会花费两倍的时间）
我认为这就是指数运行时间的定义：n延长一点，算法需要两倍的时间。
但请注意，此观察仅适用于您提出的算法。整数分解是否是多项式仍然未知。密码学家当然希望不是这样，但也有一些替代算法不依赖于素因数分解是困难的（例如椭圆曲线密码学），以防万一......