Description of the algorithm

Recall that Shor's algorithm takes as input an odd positive integer $N$ which has at least two

distict prime factors, and returns a factor of $N.$ It consists of essentially two steps

$(1)$ Pick a random integer $x$ such that $2xN-2,gcd(x,N)=1,$ and find the order

$r$ of $x$ modulo $N$ using the quantum order finding algorithm, a special case of phase

estimation.

$(2)$ If $r$ is even and $x^{\frac{r}{2}}-1(N),$ then one of $gcd(x^{\frac{r}{2}}+-1,N)$ is a non$-$trivial factor of

$N.$

Only the first step requires a quantum circuit. The calculations required in the second

step can be done efficiently on a classical computer.