algorithm - Why is factoring in NP, but not in P?

Question

Factoring: Gven an integer N, find integers 1 < a, b < N such that N = ab if they exist, otherwise say N is prime.

I know that primality testing is in P, but why not factoring?

Here is my algorithm:

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

This runs in O(sqrt(N)).

Answer 1

单个数值的输入大小由其二进制表示的长度来衡量。准确地说，输入数值的大小与n成正比log_2(n)。因此，您的算法在指数时间内运行。

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

无论如何，你测试sqrt(N)几次。但问题的大小定义为S=log2(N)。所以我们有N=2^S. 因此它是一个sqrt(2^S)=2^(S/2)指数。