Карта → событие
Шор: разложение на множители за полином — но не на этой машине
Что обещано
Стойкость RSA держится на том, что разложить большое число на множители дорого. Насколько дорого — можно посчитать. Для ключа в 2048 двоичных знаков лучший известный способ, решето числового поля, требует порядка $10^{34}$ операций. Это не «долго»: это больше, чем число секунд, прошедших от Большого взрыва, помноженное на число атомов в горе.
В ноябре 1994 года на симпозиуме по основаниям информатики Питер Шор, математик из Bell Labs, доложил алгоритм, которому та же задача стоит порядка куба длины ключа. Для тех же 2048 знаков это около девяти миллиардов шагов — работа на минуты.
Оговорка одна, и она большая: алгоритм написан не для той машины, которая стоит у вас на столе.
Почему «перебирает все варианты сразу» — неправда
Это самое частое объяснение, и оно неверное. Разберём аккуратно, потому что без этого дальше не понять ничего.
Состояние $n$ обычных переключателей — это одна строка из нулей и единиц. Состояние $n$ квантовых элементов описывается $2^{n}$ числами — амплитудами, по одной на каждую такую строку. Амплитуды комплексные, и в этом вся соль.
Дальше — то, обо что разбивается наивная картинка:
Прочитать амплитуды нельзя. Измерение возвращает ровно одну строку, и выпадает она с вероятностью, равной квадрату модуля своей амплитуды. Всё остальное исчезает безвозвратно.
То есть «посчитать функцию сразу на всех входах» действительно можно — и совершенно бесполезно: на выходе вы получите один случайный ответ, ничем не лучше подброшенной монеты.
Полезно другое. Амплитуды — числа со знаком, точнее с фазой, и они складываются. Две дороги, ведущие к одному ответу, могут усилить друг друга, а могут погасить. Вся работа квантового алгоритма — устроить вычисление так, чтобы неправильные ответы взаимно уничтожились, а правильный остался.
Ближайшая понятная аналогия
Дифракционная решётка. Свет идёт через множество щелей, от каждой — своя волна, и на экране почти везде волны гасят друг друга. Светлые полосы возникают ровно там, где фазы совпали.
Никакого «перебора» решётка не делает и ничего не «пробует». Она устроена так, что геометрия сама уничтожает всё, кроме нужного направления. Квантовый алгоритм — то же самое, только фазами управляют не щели, а последовательность операций.
Отсюда, кстати, видно, почему квантовых алгоритмов известно так мало. Придумать интерференционную картину, которая гасит именно неправильные ответы, удаётся редко: за сорок лет набралось несколько семейств, и разложение на множители — самое яркое из них.
Разложить на множители — значит найти период
Вот место, где вся красота, и оно совершенно классическое: ни одного кванта.
Возьмём число $N$ и какое-нибудь $a$, взаимно простое с ним. Посмотрим на ряд степеней по модулю $N$:
$$a^{0},\ a^{1},\ a^{2},\ a^{3},\ \ldots \pmod N.$$
Ряд обязан зациклиться, потому что остатков конечное число. Длину цикла назовём периодом $r$: это наименьшее $r$, при котором $a^{r} \equiv 1$.
Теперь фокус. Если $r$ чётно, то
$$a^{r} - 1 = \left(a^{r/2} - 1\right)\left(a^{r/2} + 1\right)$$
делится на $N$. Значит, множители $N$ распределились между двумя скобками — и найти их можно алгоритмом Евклида, которому две с половиной тысячи лет.
Разложите пятнадцать, не деля
Возьмите $N = 15$ и $a = 7$. Выпишите степени семёрки по модулю 15, найдите период, а затем наибольшие общие делители $N$ с числами $a^{r/2} \pm 1$.
(Ответ: ряд получается $1, 7, 4, 13, 1, 7, 4, 13, \ldots$ — период $r = 4$. Половина периода даёт $7^{2} = 49 \equiv 4$, дальше $\gcd(3, 15) = 3$ и $\gcd(5, 15) = 5$. Пятнадцать разложено, а делить ни на что не пришлось.
Приём срабатывает не всегда: возьмите $N = 21$ и $a = 5$. Период равен шести, $5^{3} = 125 \equiv 20 \equiv -1$, обе скобки дают $\gcd$, равный единице и самому $N$, — пустой ответ. Тогда берут другое $a$; при $a = 2$ период тоже шесть, но $2^{3} = 8$, и $\gcd(7, 21) = 7$. Вероятность неудачи меньше половины, так что двух-трёх попыток обычно хватает.)
Итог: квантовая машина нужна ровно для одного — найти период. Всё остальное в алгоритме Шора делается на обычном компьютере способами, которые старше электричества.
Где здесь ФурьеЖозеф ФурьеУтверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться.
Найти период колебания — это ровно то, для чего существует преобразование Фурье. Оно и стоит в середине алгоритма: амплитуды раскладываются по частотам, и интерференция оставляет пики там, где частота отвечает истинному периоду. Неправильные периоды гасят сами себя — та самая дифракционная решётка.
Квантовое преобразование Фурье на $n$ элементах требует порядка $n^{2}$ операций вместо $n\,2^{n}$ — и по той же причине, по которой быстро работает обычное БПФ: преобразование разбирается на маленькие одинаковые куски рекурсивным делением пополам.
И здесь стоит остановиться на географии. Быстрое преобразование Фурье опубликовано в 1965 году в Мюррей-Хилле. Шеннон работал в Мюррей-Хилле. Добеши строила всплески в Мюррей-Хилле. Шор придумал свой алгоритм там же — и главной его деталью оказалось преобразование Фурье. Спор о колеблющейся струне, начатый в Париже в 1747 году, дотянулся до угрозы всей мировой криптографии, и случилось это в одном посёлке в Нью-Джерси.
Машины, которой нет
Тут придётся быть честным, потому что вокруг много шума.
Алгоритму Шора нужны логические элементы — идеальные, не ошибающиеся. Настоящие ошибаются постоянно, и чтобы получить один надёжный, приходится связывать в исправляющий код от сотен до тысяч ненадёжных. Для ключа в 2048 знаков оценки дают миллионы физических элементов. Сегодняшние машины считают их сотнями, и они шумят.
Поэтому честный список того, что алгоритмом Шора действительно разложено, короткий: пятнадцать и двадцать один. Все громкие заголовки про разложение больших чисел на квантовых устройствах относятся к другим методам, которые к алгоритму Шора отношения не имеют и на больших числах не масштабируются.
Когда машина появится — не знает никто, и вполне возможно, что не появится вовсе.
Почему тогда это уже проблема
Из-за одной особенности секретов: они бывают долгими.
Переписку можно записать сегодня, а прочесть через двадцать лет — если к тому времени будет чем. Всё, что должно оставаться тайной десятилетиями (медицинские данные, государственная переписка, ключи, зашитые в оборудование на двадцать лет вперёд), уязвимо уже сейчас, потому что записывают уже сейчас.
Поэтому в 2016 году начался международный отбор шифров, стойких к квантовой машине, а в 2024-м приняты первые стандарты. Построены они не на теории чисел: в основе — решётки и хеш-функции, задачи совсем другой природы.
Что остаётся теории чисел
Получается симметричная развязка. Малая теорема ФермаПьер ФермаСоветник тулузского парламента, не напечатавший при жизни ни одной математической книги — и успевший заложить теорию чисел, аналитическую геометрию, метод касательных и теорию вероятностей. и функция ЭйлераЛеонард ЭйлерСамый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя. три века лежали как образец знания без всякого применения. Потом на них построили связь всей планеты — а теперь их оттуда, скорее всего, уберут, заменив решётками.
Простые числа вернутся к тому, чем были, — предмету чистого интереса. И останется третье обстоятельство, пожалуй, самое любопытное: вопрос теории чисел оказался вопросом о том, как устроена физика. Сколько стоит разложить число на множители — зависит от того, из чего сделана вселенная. Такого в этой линии ещё не было.
Соседние точки. В «Искусстве счёта»: Джонсон и Линденштраус (1984) → Шор → PageRank (1996). В дискретной: Хачиян (1979) → Шор → тот же PageRank.