8 of 8 added 2 characters in body

# Why is quantum Fourier transform required in Shor's algorithm?

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem or period of modular exponentiation sequence of some random $$x$$ such that $$1 < x < N$$.

I have no problem regarding the idea of the algorithm. But I'm wondering if Shor’s algorithm creates such a sequence by repeated squaring (which is an efficient way classically). In my understanding, the term "efficient" means that the complexity of the algorithm is polynomial in time.

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $$x^{r} = 1 \ \text{mod} N$$? During the creation process, it should not increase complexity to exponential-time, right?

Why bother with quantum Fourier transform at all? Did I misunderstand it in some way?