Здесь мы опишем один прогон квантового алгоритма, который позволяет вычислить $r$ по $M, N, t$. Мы будем использовать рабочий регистр, который может содержать пару, состоящую из переменной $0 \leqslant a \leqslant N-1$ и соответствующего значения функции $t^{a} \bmod M$. Еще один регистр будет служить рабочим полем, нужным для обратимого вычисления $\left|a, t^{a} \bmod M\right\rangle$. Когда это вычисление завершено, содержимое рабочего поля будет стерто обратимым образом (ср. с 3.2.1). В оставшейся части вычисления рабочее поле больше не будет использоваться, мы можем отделить его и забыть про него.

Квантовое вычисление состоит из четырех шагов, три из которых были описаны в разделе 3:
(i) Частичная инициализация создает из $|0,0\rangle$ суперпозицию
\[
\frac{1}{\sqrt{N}} \sum_{a=0}^{N-1}|a, 0\rangle .
\]
(ii) Обратимое вычисление $F$ преобразует это состояние в
\[
\frac{1}{\sqrt{N}} \sum_{a=0}^{N-1}\left|a, t^{a} \bmod M\right\rangle .
\]
(iii) Частичное преобразование Фурье дает
\[
\frac{1}{N} \sum_{a=0}^{N-1} \sum_{c=0}^{N-1} \exp (2 \pi i a c / N)\left|c, t^{a} \bmod M\right\rangle .
\]
(iv) Последний шаг – наблюдение этого состояния по отношению к системе классических состояний $|c, m \bmod M\rangle$. Этот шаг производит некоторый конкретный выход
\[
\left|c, t^{k} \bmod M\right\rangle
\]

с вероятностью
\[
\left|\frac{1}{N} \sum_{a: t^{a} \equiv t^{k} \bmod M} \exp (2 \pi i a c / N)\right|^{2} .
\]
На оставшейся части прогона работает классический компьютер, выполняя следующие шаги.
(A) Находится наилучшее приближение (снизу) $\kappa \frac{c}{N}$ со знаменателем $r^{\prime}<M<\sqrt{N}$ :
\[
\left|\frac{c}{N}-\frac{d^{\prime}}{r^{\prime}}\right|<\frac{1}{2 N} .
\]

Как мы увидим ниже, можно надеяться, что $r^{\prime}$ совпадет с $r$ по крайней мере в одном из не более чем полиномиального числа прогонов. Значит надо попробовать $r^{\prime}$ в роли $r$ :
(В) Если $r^{\prime} \equiv 0 \bmod 2$, то следует вычислить $\operatorname{gcd}\left(t^{r^{\prime} / 2} \pm 1, M\right)$.
Если $r^{\prime}$ нечетно или если $r^{\prime}$ четно, но мы не получили собственного делителя $M$, то следует повторить прогон $O(\log \log M)$ раз с тем же самым $t$. В случае отказа изменить $t$ и начать новый прогон.