While researching another problem, the Sieve of Eratosthenes got me wondering why it couldn’t be used to factor. After playing around, I stumbled upon an algorithm that seems like it should find factors in $O(n^2)$ time — admittedly brute-force, but still in polynomial time. Meanwhile, the GNFS is currently used to factor the largest numbers, but its time complexity is abysmal, or at least too complicated to get a good sense of what it’s doing just from looking at the notation.
What I came up with is this: for any number $n$, we know all non-trivial factors $f$ (if they exist) must satisfy $1 < f < \frac{n}{2}$. Therefore, for each integer $1 < i < \frac{n}{2}$, if $n \bmod i = 0$, $i$ is a factor of $n$. We can calculate this via counting by $i$ up to $\frac{n}{2}, \frac{n}{2}$ times. Counting by $i$ requires $i$ steps, so to reach $\frac{n}{2}$ requires $\frac{n}{2}$ steps. Doing this for every $i$ between 2 and $n/2$ requires $\frac{n}{2} - 1$ iterations.
If I’m doing my math right, $\frac{n}{2}$ steps $\times \frac{n}{2} - 1$ iterations equals $\frac{n^2}{4} - \frac{n}{2}$ total steps, which simplifies to a time complexity of $O(n^2)$, and the computer memory required should be something like $O(n \log n)$, since we don’t need to keep all the intermediate results, just the factors we generate.
So in what sense is the GNFS better than this — what am I missing?
Your algorithm is $O(N^2)$ in the number $N$ we're factoring. But when we talk about complexity of algorithms, we measure with respect to the size of the input, NOT with respect to the size of what the input represents!
For example, if we want to give $32$ to our algorithm, the actual input it receives is (in binary) $100000$, which is of size $6$. NOT of size $32$. If we want to give even $127$ to our algorithm, the actual input is $1111111$, which is of size $7$.
In general, to represent $N$, we need $\approx \log_2(N)$ many bits. Said another way, an input of size $n$ can represent numbers as large as $N = 2^n$. So an $O(N^2)$ algorithm is actually $O((2^n)^2) = O(2^{2n})$ in the size of the input, and thus is exponentially slow.
Meanwhile, the GNFS algorithm runs in time $\approx$
$$\tilde{O} \left ( 2^{C \log(N)^{1/3}} \right ) = \tilde{O} \left ( 2^{ C n^{1/3} } \right )$$
(where the $\tilde{O}$ notation means I'm suppressing some lower order terms from the big O). Of course,
$$2^{Cn^{1/3}} \ll 2^{2n}$$
so that the GNFS algorithm really is asymptotically faster. In fact, $2^{n^{1/3}}$ grows subexponentially in $n$ (but still superpolynomially) so that it's better than any algorithm that's polynomial time in $N = 2^n$.
I hope this helps ^_^