Search code examples
algorithmtime-complexitynp

Why is factoring in NP, but not in P?

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)).

Solution

  • The input size of a single numeric value, is measured by the length of its binary representation. To be precise, the size of an input numeric value n is proportional to log_2(n). Therefore your algorithm runs in expotential time.

    For instance, suppose we are factoring a number N with your algorithm. If N is prime, you have to test at least sqrt(N) factors. (Or alternatively you can compute a prime number table for this but it is still not linear).

    Anyway, you test for sqrt(N) times. But the size of the problem is defined as S=log2(N). So we have N=2^S. Therefore it's a sqrt(2^S)=2^(S/2) which is expotential.