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
