(a) Define the order of $\alpha \bmod N$ for coprime integers $\alpha$ and $N$ with $\alpha<N$. Explain briefly how knowledge of this order can be used to provide a factor of $N$, stating conditions on $\alpha$ and its order that must be satisfied.

(b) Shor's algorithm for factoring $N$ starts by choosing $\alpha<N$ coprime. Describe the subsequent steps of a single run of Shor's algorithm that computes the order of $\alpha$ mod $N$ with probability $O(1 / \log \log N)$.

[Any significant theorems that you invoke to justify the algorithm should be clearly stated (but proofs are not required). In addition you may use without proof the following two technical results.

Theorem $F T$ : For positive integers $t$ and $M$ with $M \geqslant t^{2}$, and any $0 \leqslant x_{0}<t$, let $K$ be the largest integer such that $x_{0}+(K-1) t<M .$ Let QFT denote the quantum Fourier transform $\bmod M$. Suppose we measure $Q F T\left(\frac{1}{\sqrt{K}} \sum_{k=0}^{K-1}\left|x_{0}+k t\right\rangle\right)$ to obtain an integer $c$ with $0 \leqslant c<M .$ Then with probability $O(1 / \log \log t), c$ will be an integer closest to a multiple $j(M / t)$ of $M / t$ for which the value of $j$ (between 0 and $t$ ) is coprime to $t$.

Theorem CF: For any rational number $a / b$ with $0<a / b<1$ and with integers a and $b$ having at most $n$ digits each, let $p / q$ with $p$ and $q$ coprime, be any rational number satisfying

$$\left|\frac{a}{b}-\frac{p}{q}\right| \leqslant \frac{1}{2 q^{2}} .$$

Then $p / q$ is one of the $O(n)$ convergents of the continued fraction of $a / b$ and all the convergents can be classically computed from $a / b$ in time $O\left(n^{3}\right)$.]