Why is factoring large integers considered difficult?

Problem Detail: 

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

function factor(number) -> list     factors = new list     if number < 0         factors.append(-1)         number = -number     i = 2     while i <= number         while number % i == 0             factors.append(i)             number /= i         i++     return factors 

Asked By : EnderShadow

Answered By : D.W.

You are confusing the number $n$ with the number of bits needed to represent $n$. Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$). This makes a huge difference. A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits. In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million). Then $b=21$ bits are enough to represent the number $n$. So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$. An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer_factorization

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50342