Для любого простого числа $p$ мультипликативная группа по $\bmod p$ является циклической, то есть существуют образующие $g$ такие, как $1, g, g^{2}, \ldots, g^{p-2}$, охватывающие все ненулевые вычеты по $\bmod p$ [Hardy and Wright, 1979, Tеорема 111, Knuth, 1981]. Предположим, мы задали такое простое $p$ и такую образующую $g$. Дискретным логарифмом числа $x$ по отношению к $p$ и $g$ называется целое число $r$, где $0 \leqslant r<p-1$, такое, что $g^{r} \equiv x(\bmod p)$. Самый быстрый известный алгоритм нахождения дискретного логарифма по модулю произвольного простого числа $p$ — алгоритм Гордона [1993] — видоизменения числового сита, который требует $\left.\exp \left(O(\log p)^{1 / 3}(\log \log p)^{2 / 3}\right)\right)$ шагов. Мы покажем, как находить дискретные логарифмы на квантовом компьютере с двумя возведениями в степень по модулю и двумя квантовыми преобразованиями Фурье.

Этот алгоритм будет использовать три квантовых регистра. Сначала мы найдем $q$ — степень 2 такую, чтобы $q$ была близка к $p$, то есть, чтобы $p<q<2 p$. Затем поместим в первые два регистра нашего квантового компьютера равномерную суперпозицию всех $|a\rangle$ и $|b\rangle(\bmod p-1)$ и вычислим $g^{a} x^{-b}(\bmod p)$ в третьем регистре. В peзультате наша машина останется в состоянии
\[
\frac{1}{p-1} \sum_{a=0}^{p-2} \sum_{b=0}^{p-2}\left|a, b, g^{a} x^{-b} \quad(\bmod p)\right\rangle .
\]

Как и раньше, мы применим преобразование Фурье $A_{q}$, переводя $|a\rangle \rightarrow|c\rangle$ и $|b\rangle \rightarrow|d\rangle$ с амплитудами вероятности $\frac{1}{q} \exp (2 \pi i(a c+b d) / q)$. Таким образом, мы перевели состояние $|a, b\rangle$ в состояние
\[
\frac{1}{q} \sum_{c=0}^{q-1} \sum_{d=0}^{q-1} \exp \left(\frac{2 \pi i}{q}(a c+b d)\right)|c, d\rangle
\]

а наш квантовый компьютер при этом окажется в состоянии
\[
\frac{1}{(p-1) q} \sum_{a, b=0}^{p-2} \sum_{c, d=0}^{q-1} \exp \left(\frac{2 \pi i}{q}(a c+b d)\right)\left|c, d, g^{a} x^{-b} \quad(\bmod p)\right\rangle .
\]

И наконец, произведем измерение состояния нашего квантового компьютера.

Вероятность того, что мы обнаружим состояние $|c, d, y\rangle$ с $y \equiv g^{k}(\bmod p)$ есть
\[
\left|\frac{1}{(p-1) q} \sum_{\substack{a, b \\ a-r b \equiv k}} \exp \left(\frac{2 \pi i}{q}(a c+b d)\right)\right|^{2},
\]
где сумма берется по всем $(a, b)$ таким, что $a-r b \equiv k(\bmod p-1)$. Заметим, что мы теперь имеем дело с двумя модулями, $p-1$ и $q$. Поскольку мы за этим следим, это не будет вызывать серьезных проблем. Теперь используем соотношение
\[
a=b r+k-(p-1)\left\lfloor\frac{b r+k}{p-1}\right\rfloor
\]

и подставим (6.5) в выражение (6.4) для того, чтобы получить амплитуду при $\left|c, d, g^{k} \bmod p\right\rangle$, а именно,
\[
\frac{1}{(p-1) q} \sum_{b=0}^{p-2} \exp \left(\frac{2 \pi i}{q}\left(b r c+k c+b d-c(p-1)\left\lfloor\frac{b r+k}{p-1}\right\rfloor\right)\right) .
\]

Абсолютная величина квадрата этой амплитуды есть вероятность обнаружить состояние $\left|c, d, g^{k}(\bmod p)\right\rangle$. Теперь мы проанализируем выражение (6.6). Во-первых, множитель $\exp (2 \pi i k c / q)$ может быть вынесен из всех слагаемых и им можно пренебречь, так как он не изменяет вероятности. Во-вторых, мы разложим экспоненту на две части и отфакторизуем $b$, чтобы получить
\[
\frac{1}{(p-1) q} \sum_{b=0}^{p-2} \exp \left(\frac{2 \pi i}{q} b T\right) \exp \left(\frac{2 \pi i}{q} V\right)
\]

где
\[
T=r c+d-\frac{r}{p-1}\{c(p-1)\}_{q}
\]

и
\[
V=\left(\frac{b r}{p-1}-\left\lfloor\frac{b r+k}{p-1}\right\rfloor\right)\{c(p-1)\}_{q} .
\]

Здесь под $\{z\}_{q}$ мы понимаем характер $z(\bmod q)$, при $-q / 2<\{z\}_{q} \leqslant$ $\leqslant q / 2$, как в выражении (5.7).

На следующем шаге сгруппируем возможные исходы (наблюдаемые состояния нашего квантового компьютера) на «хорошие» и «плохие». Мы покажем, что если мы получили «хорошее» конечное состояние, то, вероятно, мы получим $r$, и, более того, что вероятность получить такое «хорошее» конечное состояние постоянна. Идея заключается в том, что если
\[
\left|\{T\}_{q}\right|=\left|r c+d-\frac{r}{p-1}\{c(p-1)\}_{q}-j q\right| \leqslant \frac{1}{2},
\]

где $j$ — самое близкое целое число к $T / q$, то, так как значение $b$ заключено между 0 и $p-2$, фаза первой экспоненты в уравнении (6.7) изменяется в пределах только половины круга. Далее, если
\[
\left|\{c(p-1)\}_{q}\right| \leqslant q / 12,
\]

то $|V|$ всегда не больше $q / 12$, таким образом, фаза второй экспоненты в уравнении (6.7) изменяется от 1 до $\exp (\pi i / 6)$. Если условия (6.10) и (6.11) оба выполнены, мы можем сказать, что конечное состояние «хорошее». Мы покажем, что если эти условия выполнены, то вклад в вероятность от соответствующих членов существенен. Более того, оба условия будут выполнены с постоянной вероятностью, а разумное предположение о значении $c$ в этих условиях (6.10) позволят нам получить $r$.

Сейчас мы определим нижнюю границу вероятности такого положительного исхода, то есть, исхода, удовлетворяющего условиям (6.10) и (6.11). Мы знаем, что $b$ изменяется от 0 до $p-2$, фаза $\exp (2 \pi i b T / q)$ изменяется от 0 до $2 \pi i W$, где
\[
W=\frac{p-2}{q}\left(r c+d-\frac{r}{p-1}\{c(p-1)\}_{q}-j q\right) .
\]

Из (6.10) следует, что $|W| \leqslant(p-2) /(2 q) \leqslant 1 / 2$. Поэтому составная часть амплитуды первой экспоненты в слагаемом (6.7) в направлении
\[
\exp (\pi i W)
\]

есть по крайней мере $\cos (2 \pi|W / 2-W b /(p-2)|)$, где $2 \pi(W / 2-$ $-W b /(p-2))$ лежит между $-\pi / 2$ и $\pi / 2$.

Из условий (6.11) фаза может изменяться до $\pi i / 6$ благодаря второй экспоненте $\exp (2 \pi i V / q)$. Используя это изменение для того, чтобы минимизировать составляющую в направлении (6.13), мы получим, что эта составляющая в данном направлении не меньше
\[
\cos \left(2 \pi|W / 2-W b /(p-2)|+\frac{\pi}{6}\right) .
\]
Таким образом, мы получаем, что абсолютная величина амплитуды (6.7) будет каю минимум
\[
\frac{1}{(p-1) q} \sum_{b=0}^{p-2} \cos \left(2 \pi|W / 2-W b /(p-2)|+\frac{\pi}{6}\right) .
\]

Заменяя здесь сумму на интеграл, получим, что абсолютная величина амплитуды не меньше
\[
\frac{2}{q} \int_{0}^{1 / 2} \cos \left(\frac{\pi}{6}+2 \pi|W| u\right) d u+O\left(\frac{W}{p q}\right) .
\]

Из условий $(6.10),|W| \leqslant \frac{1}{2}$, таким образом, ошибка составит $O\left(\frac{1}{p q}\right)$. Так как $W$ изменяется от $-\frac{1}{2}$ до $\frac{1}{2}$, интеграл (6.16) минимизируется, когда $|W|=\frac{1}{2}$. Тогда вероятность обнаружить состояние $|c, d, y\rangle$, которое удовлетворяет обоим условиям (6.10) и (6.11), как минимум
\[
\left(\frac{1}{q} \frac{2}{\pi} \int_{\pi / 6}^{2 \pi / 3} \cos u d u\right)^{2}
\]

или не меньше $0.054 / q^{2}>1 /\left(20 q^{2}\right)$.
Сосчитаем теперь пары чисел $(c, d)$, удовлетворяющие условиям (6.10) и (6.11). Число пар $(c, d)$, удовлетворяющих (6.10) в точности равно числу возможных значений $c$, так как для каждого $c$ существует одно такое $d$, что (6.10) выполнено. Если $\operatorname{gcd}(p-1, q)$ не велик, число таких $c$, для которых выполняется условие (6.11), приблизительно равно $q / 6$, и даже если он велик, таких чисел по крайней мере $q / 12$. Следовательно, существует по крайней мере $q / 12$ пар $(c, d)$, удовлетворяющие обоим условиям. Умножая все на $p-1$, число возможных значений $y$, получим приближенное количество хороших состояний $|c, d, y\rangle-p q / 12$. Комбинируя данное вычисление с нижней границей обнаружения такого хорошего состояния — $1 /\left(20 q^{2}\right)$, получим, что вероятность положительного исхода не менее $p /(240 q)$, или по крайней мере $1 / 480$ (так
как $q<2 p$ ). Заметим, что каждое хорошее значение $c$ имеет вероятность быть обнаруженной не менее $(p-1) /\left(20 q^{2}\right) \geqslant 1 /(40 q)$, так как здесь $p-1$ значений $y$ и какое-то одно значение $d$, для каждого $c$ может образовать хорошее состояние $|c, d, y\rangle$.
Теперь мы хотим извлечь $r$ из пары $c, d$ таких, что
\[
-\frac{1}{2 q} \leqslant \frac{d}{q}+r\left(\frac{c(p-1)-\{c(p-1)\}_{q}}{(p-1) q}\right) \leqslant \frac{1}{2 q} \bmod 1,
\]

где это уравнение может быть получено из условий (6.10) посредством деления на $q$. Первое, что мы отметим, что множитель при $r$ сократится со знаменателем $p-1$, так как $q$ без остатка делит $c(p-1)-$ $-\{c(p-1)\}_{q}$. Поэтому нам надо только округлить $d / q$ до ближайшего кратного $1 /(p-1)$ числа, разделить по $\bmod (p-1)$ на целое число
\[
c^{\prime}=\frac{c(p-1)-\{c(p-1)\}_{q}}{q}
\]

и найти вариант $r$. Чтобы показать, что для того, чтобы найти правильное $r$ за полиномиальное число повторений этого квантового вычисления, нам потребуются прояснить еще некоторые детали. Проблема заключается в том, что мы не можем делить на число $c^{\prime}$, которое не является взаимно простым с $p-1$.

Для алгоритма отыскания дискретных логарифмов мы не знаем, что все возможные значения $c^{\prime}$ генерируются с разумной точностью, мы это можем сказать только о их двенадцатой части. Эта дополнительная трудность делает следующий шаг более сложным, чем соответствующий шаг в алгоритме факторизации. Если бы мы знали остаток $r$ по модулю всех простых степеней, делящихся на $p-1$, мы могли бы использовать для извлечения $r$ за полиномиальное время Китайскую теорему об остатке. Мы можем доказать только, что мы в состоянии найти этот остаток для простых чисел, больших, чем 18 , но после небольшой дополнительной работы мы все-таки окажемся в состоянии извлечь $r$.

Вспомним, что каждая хорошая пара $(c, d)$ генерируется с вероятностью по крайней мере равной $1 /\left(20 q^{2}\right)$, и что каю минимум двенадцатая часть всех возможных $c$ принадлежит к хорошей $(c, d)$ паpe. Из уравнения (6.19) следует, что такие $c$ отображаются из $c / q$
в $c^{\prime} /(p-1)$ посредством округления их до ближайшего целого, умноженного на $1 /(p-1)$. Далее, хорошими $c$ являются в точности те, для которых $c / q$ близко к $c^{\prime} /(p-1)$. Поэтому каждое хорошее $c$ связано с только одним $c^{\prime}$. Мы хотим показать, что для любой простой степени $p_{i}^{\alpha_{i}}$, делящейся на $p-1$, маловероятно, что произвольное хорошее $c^{\prime}$ содержит $p_{i}$. Если мы примем в рассмотрение в нашем алгоритме большие величины, мы сразу можем игнорировать простые степени ниже 18 . Если мы знаем, что $r$ по модулю всех простых степеней больше 18 , мы можем попытаться использовать все возможные вычеты для простых чисел меньших 18 только с растущим со временем (большим) постоянным множителем. Так как минимум одна двенадцатая часть всех $c$ является хорошей для пары $(c, d)$, то по крайней мере одна двенадцатая часть $c^{\prime}$ тоже хороша. Поэтому для простой степени $p_{i}^{\alpha_{i}}$ произвольное хорошее $c^{\prime}$ делится на $p_{i}^{\alpha_{i}}$ с вероятностью не большей $12 / p_{i}^{\alpha_{i}}$. Если у нас есть $t$ хороших $c^{\prime}$, то, следовательно, вероятность того, что существует такая простая степень, большая 18 , которая делит любое из них, не больше
\[
\sum_{18<p_{i}^{\alpha_{i}} \mid(p-1)}\left(\frac{12}{p_{i}^{\alpha_{i}}}\right)^{t},
\]

где через $a \mid b$ обозначаются те $a$, которые нацело делятся на $b$, таким образом, сумма берется по всем простым степеням, большим чем 18 , которые делятся на $p-1$. Такая сумма (по всем целым числам $>18$ ) для $t=2$ сходится, и уменьшается далее по крайней мере на множитель $2 / 3$ при каждом дальнейшем увеличении $t$ на 1 . Таким образом, для некоторого постоянного $t$ она станет меньше $1 / 2$.

Напомним, что каждая хорошая $c^{\prime}$ получается с вероятностью не меньшей, чем $1 /(40 q)$ при каждом эксперименте. Поскольку мы будем иметь $q / 12$ хороших $c^{\prime}$ после $480 t$ экспериментов, то мы, вероятно, получим пример $t$ хороших $c^{\prime}$, выбранных приблизительно равномерно из всех $c^{\prime}$. Таким образом, мы будем в состоянии найти такое множество $c^{\prime}$, что все простые степени $p_{i}^{\alpha_{i}}>20$, делящиеся на $p-1$, взаимно просты по крайней мере с одним из таких $c^{\prime}$. Для того чтобы получить полиномиальный по времени алгоритм, необходимо перебрать все возможные множества $c^{\prime}$ размера $t$; на практике можно было бы использовать алгоритм нахождения множеств $c^{\prime}$ с большими общими множителями. Такое множество дает вычет $r$ для всех простых целых чисел, больших, чем 18. Для каждого простого $p_{i}$, меньшего 18 , мы имеем не меньше 18 вариантов для характера по модулю $p_{i}^{\alpha_{i}}$, где $\alpha_{i}$ — показатель степени у простого числа $p_{i}$ при факторизации на простые сомножители $p-1$. Таким образом, мы можем перебрать все возможные вычеты по модулю степеней простых чисел меньших 18: для таких возможностей мы можем вычислить соответствующую $r$, используя Китайскую теорему об остатке, и тогда проверить, является ли он требуемым дискретным логарифмом.

Если будет создана реальная программа по этому алгоритму, ее эффективность может по многим причинам увеличиться по сравнению с эффективностью, показанной в работе. Например, оценка для числа хороших $c^{\prime}$ вероятно сильно занижена, так как более мягких условий, чем (6.10) и (6.11), должно быть достаточно. Это означает, что число требуемых повторений должно сократиться. Также кажется неправдоподобным, что распределение плохих значений $c^{\prime}$ становится другим для простых чисел, меньших 18 ; если это действительно так, то нам не надо специальным образом трактовать малые простые степени.

Этот алгоритм не пользуется многими свойствами $\mathbb{Z}_{p}$, и, таким образом, мы можем использовать подобный алгоритм и в других полях, таких как $\mathbb{Z}_{p^{\alpha}}$, так же как и в поле, имеющем циклическую мультипликативную группу. Все, что нам надо, это знать порядок генератора, и что мы можем умножать и искать обратные элементы за полиномиальное время. В действительности, порядок генератора может быть вычислен с использованием квантового алгоритма нахождения порядка, который описан в $§ 5$ этой статьи. В работе Boneh и Lipton [1995] алгоритм обобщен и дает возможность найти дискретный логарифм, когда группа абелева, но не циклическая.