Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Мы хотим факторизовать число $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\}$ выглядят, соответственно, как Число $r$ – это минимальная степень, для которой $x^{r}=1(\bmod N)$. Давайте предположим, что описанным выше алгоритмом квантовых вычислений мы получили период $r$ [26]. Если этот период четный, мы можем приступить к нашему алгоритму факторизации. Если нет, мы должны выбрать другое $x$ и начать сначала. Случайным образом выбранное $x$ приведет к подходящему четному периоду $r$ в пятидесяти процентах случаев, поэтому понадобится не так много попыток $[1,2]$. Приступим теперь к алгоритму факторизации. Выбрав $x$ так, что последовательность $\left\{x^{a}(\bmod N)\right\}$ имеет четный период $r$, перепишем соотношение $x^{r}=1(\bmod N)$ как разность двух квадратов: Выражая левую сторону как произведение суммы и разности, получим Это просто означает, что произведение двух сомножителей слева кратно числу $N$, которое мы хотим факторизовать. Таким образом, или один, или другой сомножитель должен иметь общий множитель с $N$. Окончательный этап алгоритма состоит в вычислении наибольшего общего делителя каждого из этих сомножителей с $N$ (эффективный классический алгоритм описан в приложении). Любой нетривиальный общий делитель является множителем, который мы искали. Таким образом, поиск будет завершен. В качестве примера рассмотрим число $N=91$. Выбирая $x=3$, найдем, что последовательность $3^{a}(\bmod 9) 1$ имеет вид Квантовый компьютер может вычислять период параллельно, однако здесь достаточно взглянуть невооруженным глазом, чтобы заметить, что последовательность имеет период $r=6$ (так как он четный, можно приступать к алгоритму).
|
1 |
Оглавление
|