Мы хотим факторизовать число $N$. Достаточно найти хотя бы один множитель, так как затем мы можем свести задачу к более простой. Прежде всего, выберем число $x$.

С помощью алгоритма Евклида (см. приложение) можно эффективно вычислить общие множители у $N$ и $x$, и редуцировать задачу. Поэтому предположим, что эти числа взаимно просты. Затем рассмотрим последовательность, образованную функцией $f(a)=x^{a}(\bmod N)$. Здесь $a(\bmod b)$ обозначает остаток от деления $a$ на $b$. Он может пониматься как час, показываемый на циферблате с $b$ делениями после того, как прошло $a$ часов с тех пор, когда часы были поставлены на нулевой час (час $b$ ).

Последовательности $\left\{x^{a}\right\}$ и $\left\{x^{a}(\bmod N)\right\}$ выглядят, соответственно, как
\[
\begin{array}{c}
1, x, \ldots, x^{r-1}, x^{r}, x^{r+1}, \ldots \\
\underbrace{1, x, \ldots,}_{r \text { членов }}, \underbrace{1, x, \ldots,}_{r \text { членов }}, \underbrace{1, x, \ldots,}_{r \text { членов }},
\end{array}
\]

Число $r$ — это минимальная степень, для которой $x^{r}=1(\bmod N)$.
Пристальный взгляд на нижнюю последовательность обнаружит, что она имеет периодическую структуру с периодом $r$. Используя стандартные алгоритмы, этот период для длинных последовательностей получить весьма непросто. Однако описанным в предыдущем разделе алгоритмом для квантового компьютера он может быть вычислен эффективным образом. Эта возможность, как мы сейчас продемонстрируем, открывает новый способ найти множители числа $N$.

Давайте предположим, что описанным выше алгоритмом квантовых вычислений мы получили период $r$ [26]. Если этот период четный, мы можем приступить к нашему алгоритму факторизации. Если нет, мы должны выбрать другое $x$ и начать сначала. Случайным образом выбранное $x$ приведет к подходящему четному периоду $r$ в пятидесяти процентах случаев, поэтому понадобится не так много попыток $[1,2]$.

Приступим теперь к алгоритму факторизации. Выбрав $x$ так, что последовательность $\left\{x^{a}(\bmod N)\right\}$ имеет четный период $r$, перепишем соотношение $x^{r}=1(\bmod N)$ как разность двух квадратов:
\[
\left(x^{r / 2}\right)^{2}-1 \equiv 0 \quad(\bmod N) .
\]

Выражая левую сторону как произведение суммы и разности, получим
\[
\left(x^{r / 2}+1\right)\left(x^{r / 2}-1\right) \equiv 0 \quad(\bmod N) .
\]

Это просто означает, что произведение двух сомножителей слева кратно числу $N$, которое мы хотим факторизовать. Таким образом, или один, или другой сомножитель должен иметь общий множитель с $N$. Окончательный этап алгоритма состоит в вычислении наибольшего общего делителя каждого из этих сомножителей с $N$ (эффективный классический алгоритм описан в приложении). Любой нетривиальный общий делитель является множителем, который мы искали. Таким образом, поиск будет завершен.

В качестве примера рассмотрим число $N=91$. Выбирая $x=3$, найдем, что последовательность $3^{a}(\bmod 9) 1$ имеет вид

Квантовый компьютер может вычислять период параллельно, однако здесь достаточно взглянуть невооруженным глазом, чтобы заметить, что последовательность имеет период $r=6$ (так как он четный, можно приступать к алгоритму).
Переписывая соотношение $3^{6} \equiv 1(\bmod 9) 1$ как сказано выше, получим $28 \times 26 \equiv 0(\bmod 9) 1$. Это означает, что либо НОД $(28,91)$, либо НОД $(26,91$ ) являются нетривиальными делителями 91 . В действительности, в этом случае оба члена дают различные множители, соответственно, 7 и 13. Это завершает разложение числа 91 на простые множители: $91=7 \times 13$.