Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Для любого простого числа $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зультате наша машина останется в состоянии Как и раньше, мы применим преобразование Фурье $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$ в состояние а наш квантовый компьютер при этом окажется в состоянии И наконец, произведем измерение состояния нашего квантового компьютера. Вероятность того, что мы обнаружим состояние $|c, d, y\rangle$ с $y \equiv g^{k}(\bmod p)$ есть и подставим (6.5) в выражение (6.4) для того, чтобы получить амплитуду при $\left|c, d, g^{k} \bmod p\right\rangle$, а именно, Абсолютная величина квадрата этой амплитуды есть вероятность обнаружить состояние $\left|c, d, g^{k}(\bmod p)\right\rangle$. Теперь мы проанализируем выражение (6.6). Во-первых, множитель $\exp (2 \pi i k c / q)$ может быть вынесен из всех слагаемых и им можно пренебречь, так как он не изменяет вероятности. Во-вторых, мы разложим экспоненту на две части и отфакторизуем $b$, чтобы получить где и Здесь под $\{z\}_{q}$ мы понимаем характер $z(\bmod q)$, при $-q / 2<\{z\}_{q} \leqslant$ $\leqslant q / 2$, как в выражении (5.7). На следующем шаге сгруппируем возможные исходы (наблюдаемые состояния нашего квантового компьютера) на «хорошие» и «плохие». Мы покажем, что если мы получили «хорошее» конечное состояние, то, вероятно, мы получим $r$, и, более того, что вероятность получить такое «хорошее» конечное состояние постоянна. Идея заключается в том, что если где $j$ – самое близкое целое число к $T / q$, то, так как значение $b$ заключено между 0 и $p-2$, фаза первой экспоненты в уравнении (6.7) изменяется в пределах только половины круга. Далее, если то $|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$, где Из (6.10) следует, что $|W| \leqslant(p-2) /(2 q) \leqslant 1 / 2$. Поэтому составная часть амплитуды первой экспоненты в слагаемом (6.7) в направлении есть по крайней мере $\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), мы получим, что эта составляющая в данном направлении не меньше Заменяя здесь сумму на интеграл, получим, что абсолютная величина амплитуды не меньше Из условий $(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), как минимум или не меньше $0.054 / q^{2}>1 /\left(20 q^{2}\right)$. где это уравнение может быть получено из условий (6.10) посредством деления на $q$. Первое, что мы отметим, что множитель при $r$ сократится со знаменателем $p-1$, так как $q$ без остатка делит $c(p-1)-$ $-\{c(p-1)\}_{q}$. Поэтому нам надо только округлить $d / q$ до ближайшего кратного $1 /(p-1)$ числа, разделить по $\bmod (p-1)$ на целое число и найти вариант $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$ где через $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] алгоритм обобщен и дает возможность найти дискретный логарифм, когда группа абелева, но не циклическая.
|
1 |
Оглавление
|