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

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

StackExchange Computer Science Q#50342, answer score: 26