Prime Factorization Time Complexity

[gchadwick]

While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm.

First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others) a very simple way to do it is to simple divide the number you're trying to factorize, n by every number between 2 and sqrt(n) and seeing which two leave no remainder. If we then say that the division has a time complexity of o(a) where a is the number of digits we can work out the time complexity of factorization by a simple sum, log(n) + log(n) + log(n) + ... + log(n) (where log(n) will be the number of digits in n) the sum will have sqrt(n) terms in giving sqrt(n) log(n) however that is clearly the wrong result, so can anyone tell me where I'm going wrong? I'm sure it's something obvious I just can't see it.

 

[vsage]

While I know the time complexity for all known prime factorization algorithms is exponential

Are you sure about that? If you're correct then I have the same stumbling block as you, because even an algorithm that tests all numbers 1 to N would only have a run time of NlogN

 

[Hurkyl]

If you're correct then I have the same stumbling block as you, because even an algorithm that tests all numbers 1 to N would only have a run time of NlogN]

That is an exponential algorithm: the complexity of number theoretic algorithms is usually described in terms of the size of the representation of the numbers involved, rather than the size of the numbers themselves.

It takes n = lg N bits to store the number N, and so this algorithm runs in time:

$$O(2^{\mathop{\text{lg}} N} \mathop{\text{lg}} N)<br /> = O(2^n n)$$

and is thus exponential.


That said, prime factorization is known to be subexponential: The number field sieve is an L(1/3) algorithm. See Wikipedia's or Mathworld's page for reference.

 

[gchadwick]

Ahh that makes sense, I knew it was something obvious, thanks :)