For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the function $a^k \bmod N$ with the ultimate goal of finding the k that solves $a^k \bmod N = 1$.
Acknowledging that it would be impractically slow, I would like to write a version that uses the classical FFT. Certainly such an algorithm could factor small numbers.
What confuses me is that when I calculate the values of $a^k \bmod N$ to feed into the FFT, it is not that much harder skip the FFT and just find $a^k \bmod N = 1$ by brute force (similar to this question).
What am I missing here? Alternatively, if I had a black box that could calculate FFTs instantaneously, how would this change Shor's algorithm?