I’m recently studying the Shor’s algorithm and got confused about the matter of complexity.

What I have read through that Shor’s algorithm reduce the factorization problem to order-finding problem or period of modular exponentiation sequence of some random x such that 1 < x N.

I have no problem about the idea of an algorithm. But wondering that if Shor’s algorithm creates such a sequence by repeated squaring which is can an efficient way classically

In my understand the efficient mean that the complexity of algorithm is polynomial in time of a problem.

So if there is efficient way to do create the sequence classically, then can we just add a little check if we have encountered $x^{r} = 1 mod N$ or not during the creating process it should not increase complexity to be exponential-time right? Why bothering Quantum Fourier transform at all ?

Or I miss understand its in some way.

And the next question is when one what to obtain a period from measurement result by using an continued fraction approximation. By consider an example of N = 21 and random number to construct a modular exponentiation sequence is x = 2 from (Shor's Algorithm for Factoring Large Integers)1 then this paper state that

There are six possible result after measuring the state after quantum Fourier transform which is

0 return period —> fail , 85 return period —> 6 , 171 return period —> 3 , 256 return period —> 2 , 341 return period —> 3 , 427 return period —> 6

Which the expect result should be 6

It can be see that the probability that the algorithm successfully return the right answer in the first run is around 33%

But the paper state that if the measurement return third to fifth possibly result (171,256,341) that is a factor of a period ($r = r_{1}r_{2}$) you can use $2^r mod 21$ be a new $x$ to run an algorithm again which there is some probability of return other factor of period ($r_{2}$) so the sum-up probability of successfully return period r is around 61% (in paper is 55% but I tried calculate myself is 61%, sorry if any mistake)

So the second question is which way is more efficient or right way to do this, either run algorithm again with new random $x$ or to correct the period with $x = 2^{r_{1}} mod N$

And what is probability of return the right answer for other $N$ and $x$ of Shor’s algorithm in either way and maybe proof of such a probability.

Thank you in advance