Building the period-finding circuit for Shor's Algorithm & the classical complexity of finding the period

Question

I've been trying to learn about Shor's algorithm by writing out implementations of the circuit for modular exponentiation, ${ a }^{ x }\; ({ mod }\; N)$, to find the period $r$ for small numbers such as:

$(N=15,\quad a=11)\quad \longrightarrow \quad r=2$,

$(N=35,\quad a=13)\quad \longrightarrow \quad r=4$,

$(N=21,\quad a=5)\quad \longrightarrow \quad r=6$.

I know these are incredibly small numbers, but I realised that in order to actually start building the cicuit at all (using the binary exponentiation method), I needed to calculate the values of ${ a }^{ { 2 }^{ k } }\; ({ mod }\; N)$ for all $0\;\le\;k \; <\; 2\; \lceil { \log _{ 2 }{ N } }\rceil $, which pretty much immediately made the values of $r$ obvious before I'd even started building the circuit.

For example, take the least trivial case from the above, where $r=6$. I needed to calculate:

${ 5 }^{ 0 }\; ({ mod }\; 21)=1$,

${ 5 }^{ 1 }\; ({ mod }\; 21)=5$,

${ 5 }^{ 2 }\; ({ mod }\; 21)=4$,

${ 5 }^{ 4 }\; ({ mod }\; 21)=16$,

${ 5 }^{ 8 }\; ({ mod }\; 21)=4$,

${ 5 }^{ 16 }\; ({ mod }\; 21)=16$.

Simply by inspection, I can already see what the value of $r$ must be, because the result is the same when $x$ increases by six or twelve, but not after increasing by two or three.

I therefore have two questions:

1. Is calculating these modular exponentials of $a$ to powers of two required when building these circuits, or is there some way of not even having to do that?

2. If we do need to calculate these values, can we not find the period $r$ of this modular exponentiation function classically in an efficient way, starting with these values and then using a method analogous to 'interval halving', or an I being misled by using small numbers? [SEE EDIT]

Thanks in advance!

EDIT: As Mark S points out, the results of modular exponentiation have very little structure, and so although perhaps faster than $O(N)$, such an 'interval halving' method would not have logarithmic complexity, thus would be slower than Shor's algorithm for large enough $N$.

Answer 1

The fast "modular exponentiation by repeated-squaring" part of Shor's algorithm is only one of the many ideas in Shor's paper, and I think a more critical idea/breakthrough is the QFT itself. However, without something equivalent to modular exponentiation by repeated-squaring, you have no way of having a small circuit to evaluate $f(x)$, so that you can perform the QFT on $\vert x\rangle\vert f(x)\rangle$.

I also think you are being significantly misled by looking at such small numbers. You'll need to prepare a state $\vert x\rangle\vert f(x)\rangle$ somehow; here $f(x)$ is evaluated with repeated-squaring, which is honestly pretty darned fast already, when $x$ gets large. It's not clear if a "binary search" is not already what the repeated-squaring is effectively doing.