# Why is factoring large integers considered difficult?

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

– Raphael
Dec 5 '15 at 9:26
• That algorithm is actually very slow - if number is a prime number the loop while iterate (number) times. There is a very simple argument that allows you getting away with sqrt (number) iterations. Dec 5 '15 at 16:18

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.

• I knew it was something simple like that. Dec 5 '15 at 5:57
• @EnderShadow: Also, the kind of numbers whose factoring is considered hard using currently available hardware, and used e.g. in RSA encryption, have $b > 1{,}000$ (i.e. $n > 2^{1{,}000}$) or so. As an exercise, assuming that you computer can run your $O(n)$ algorithm at, say, one billion iterations per second, calculate how many years it would take to factor $n \approx 2^{1{,}000}$. (If your initial reaction is "that can't be right!", you've probably calculated it correctly.) Dec 5 '15 at 12:51

you have roughly two questions here, a general and a specific one about your code. the specific one is handled in the other answer. the general question in the title about the complexity of factoring is very deep. unfortunately there is not strong scientific evidence that factoring is outside of P other than (the mostly circumstantial) "lots of experts have tried and failed" and some experts conjecture it is inside P; its regarded as one of the foremost (and very hard to resolve) open problems of complexity theory. after decades of "heavy attack" the best algorithms are exponential. factoring complexity is one of the "few exceptional problems" that is known to lie "between" P and NP complete but has not been classified as either so far.

as is pointed out, the complexity was not much of an issue until it became used ("roughly") in the RSA cryptosystems in the mid 1980s where cryptographic security depends on the assumption. (two other "not-exactly-encouraging" related datapoints: Shors algorithm for P-time quantum factoring and primality testing was proven to be in P in the early 2000s in the famous/ celebrated AKS algorithm.) a possible positive outcome would be that its in quasipolynomial time, which is weaker than NP complete (assuming P≠NP and NP complete has an exponential time lower bound) but still technically "hard".