Алгоритм Шора: зачем он ломает RSA и как работает

Алгоритм Шора - это квантовый алгоритм факторизации, который раскладывает большое составное число $N$ на простые множители за время, полиномиальное от числа битов $\log N$, тогда как лучшие известные классические методы (решето числового поля) работают субэкспоненциально. Предложенный Питером Шором в 1994 году, он стал главным примером экспоненциального квантового ускорения и прямой угрозой криптосистеме RSA, чья стойкость опирается именно на вычислительную сложность факторизации. Ключевая идея - не «искать делители» в лоб, а свести задачу к поиску периода функции и решить эту подзадачу квантовым преобразованием Фурье. Ниже разберём всю цепочку: классическую редукцию, квантовое ядро и то, почему RSA оказывается под ударом.

Сведение факторизации к поиску периода

Алгоритм Шора факторизации не атакует число напрямую. Он опирается на классический теоретико-числовой факт: чтобы разложить нечётное составное $N$, достаточно научиться находить период функции возведения в степень по модулю. Выберем случайное $a$ из диапазона $1 < a < N$ и проверим $\gcd(a, N)$ алгоритмом Евклида. Если он больше единицы - нам повезло, нетривиальный делитель уже найден без всякого кванта. Если же $\gcd(a, N) = 1$, переходим к интересному случаю и рассматриваем функцию

$f(x) = a^x \bmod N.$

Эта функция периодична: существует наименьшее $r > 0$, для которого $a^r \equiv 1 \pmod N$. Число $r$ называется порядком элемента $a$ по модулю $N$, и именно его поиск - сердце алгоритма. Найдя период $r$, мы возвращаемся к множителям почти бесплатно, и удобно сразу прогнать конкретные числа: какой период у выбранного $a$, чётный ли он и какие делители из него получаются.

От периода к множителям

Пусть период $r$ найден. Чтобы извлечь делитель, нужны два условия: $r$ должно быть чётным и при этом $a^{r/2} \not\equiv -1 \pmod N$. Тогда из соотношения $a^r \equiv 1$ следует

$a^r - 1 = \left(a^{r/2} - 1\right)\left(a^{r/2} + 1\right) \equiv 0 \pmod N,$

то есть $N$ делит произведение $(a^{r/2}-1)(a^{r/2}+1)$, но не делит ни один из множителей по отдельности. Значит, $\gcd(a^{r/2} - 1, N)$ и $\gcd(a^{r/2} + 1, N)$ дают нетривиальные делители $N$. Оба наибольших общих делителя считаются классическим алгоритмом Евклида мгновенно.

Если условие чётности или неравенства нарушено, выбранное $a$ «не сработало» - тогда берут другое случайное $a$ и повторяют. Можно показать, что для случайного $a$ оба условия выполняются с вероятностью не меньше $1/2$ (для $N$ с хотя бы двумя различными нечётными простыми делителями), поэтому в среднем хватает нескольких попыток. Вся эта часть - чисто классическая; квант нужен ровно для одного: быстро найти период $r$.

Почему классике период не по зубам

Возникает резонный вопрос: если поиск периода так помогает, почему его нельзя сделать на обычном компьютере? Проблема в том, что период $r$ может быть огромным - порядка самого $N$, то есть экспоненциальным от длины записи числа. Перебирать степени $a^1, a^2, a^3, \dots$ до возврата к единице - это до $\sim N$ операций, что не лучше прямого перебора делителей. Никакого классического алгоритма, находящего порядок элемента быстрее чем за субэкспоненциальное время, не известно - задача поиска периода вычислительно эквивалентна факторизации.

Квантовый компьютер обходит это за счёт того, что вычисляет $f(x) = a^x \bmod N$ сразу на суперпозиции всех аргументов и затем извлекает спрятанную в этой суперпозиции периодичность одним глобальным преобразованием. Именно здесь и возникает экспоненциальное ускорение алгоритма Шора, которого лишён, например, алгоритм Гровера с его квадратичным выигрышем.

Квантовое ядро: суперпозиция и оценка фазы

Квантовая часть работает с двумя регистрами. Первый, «считающий», содержит $t$ кубитов (берут $t \approx 2\log_2 N$, чтобы хватило разрешения); второй хранит значения функции. Сначала каскад адамаровых вентилей переводит первый регистр в равномерную суперпозицию всех аргументов:

$|\psi\rangle = \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t - 1} |x\rangle |0\rangle.$

Затем обратимая схема модульного возведения в степень вычисляет $f(x)$ во второй регистр, запутывая регистры:

$|\psi\rangle = \frac{1}{\sqrt{2^t}} \sum_{x} |x\rangle\, |a^x \bmod N\rangle.$

Это и есть «квантовый параллелизм»: одно применение унитарной схемы посчитало функцию на всех $2^t$ входах одновременно. Но просто измерить регистр нельзя - мы получим одно случайное значение и потеряем периодичность. Чтобы её выявить, к первому регистру применяют квантовое преобразование Фурье.

Квантовое преобразование Фурье и считывание периода

Квантовое преобразование Фурье (QFT) - это унитарный аналог дискретного преобразования Фурье, действующий на амплитуды:

$\text{QFT}\,|x\rangle = \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i\, x k / 2^t} |k\rangle.$

Его ключевое достоинство - глубина схемы всего $O(t^2)$ (а с приближением и того меньше), тогда как классическое БПФ требует $O(t\,2^t)$ операций. Применённый к регистру, хранящему периодическую по $x$ структуру, QFT концентрирует амплитуду вблизи значений $k$, кратных $2^t / r$. После измерения мы с высокой вероятностью получаем такое $k$, что

$\frac{k}{2^t} \approx \frac{s}{r}, \qquad s \in \mathbb{Z}.$

Дробь $s/r$ извлекают из измеренного $k/2^t$ методом непрерывных дробей - классическая постобработка, которая по приближённому значению восстанавливает несократимую дробь со знаменателем $r$. Несколько прогонов (или одна удачная пара измерений) позволяют надёжно определить сам период $r$. По сути вся квантовая магия - это оценка фазы (phase estimation) собственного значения оператора умножения на $a$, и поиск периода - частный случай более общей задачи о скрытой подгруппе.

Сложность и угроза для RSA

Полная стоимость алгоритма Шора факторизации определяется самой дорогой подсхемой - модульным возведением в степень, которое доминирует над QFT. Аккуратные оценки дают $O\big((\log N)^2 (\log\log N)(\log\log\log N)\big)$ элементарных операций или $\tilde O\big((\log N)^2\big)$ в упрощённой записи - полином от длины числа. Для сравнения, решето числового поля раскладывает $N$ за $\exp\!\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$ - субэкспоненциально, и именно эта граница делает RSA-2048 неприступным для классических машин.

Стойкость RSA эквивалентна сложности факторизации модуля $N = pq$: зная разложение, легко вычислить функцию Эйлера и закрытый ключ. Полиномиальный квантовый алгоритм Шора эту защиту обнуляет - поэтому появление масштабируемого квантового компьютера сделает текущий RSA взламываемым. Тот же поиск периода/дискретного логарифма ломает и схемы на эллиптических кривых, и протокол обмена ключами Диффи - Хеллмана. Ответ индустрии - переход на постквантовую криптографию (решёточные схемы вроде Kyber), стойкость которых не сводится к факторизации или дискретному логарифму.

Где предел на практике

Несмотря на теоретическую мощь, физическая реализация остаётся скромной. Демонстрации факторизуют крошечные числа (классический показательный пример - $15 = 3 \times 5$), а «рекорды» вроде разложения больших чисел нередко используют упрощённые схемы, заранее подогнанные под ответ, и не масштабируются. Главный барьер - число логических кубитов и глубина схемы: для RSA-2048 нужны тысячи логических кубитов, а с учётом квантовой коррекции ошибок - миллионы физических. Шумные NISQ-устройства такой когерентности пока не держат, поэтому реальный взлом RSA - вопрос инженерии отказоустойчивых кубитов, а не теории: алгоритм уже готов и доказанно корректен.

Частые ошибки

• Думают, что алгоритм Шора «перебирает делители быстрее». Нет - он вообще не ищет делители напрямую, а решает задачу поиска периода функции $a^x \bmod N$.
• Считают, что весь алгоритм квантовый. Квантовая только подзадача поиска периода; редукция, НОД по Евклиду и непрерывные дроби - классические.
• Путают ускорение Шора и Гровера. Шор даёт экспоненциальный выигрыш для факторизации, Гровер - лишь квадратичный для неструктурированного поиска.
• Забывают про условия на период: если $r$ нечётно или $a^{r/2} \equiv -1 \pmod N$, попытка бесполезна и нужно новое случайное $a$.
• Полагают, что Шор уже ломает RSA сегодня. Алгоритм корректен, но требует тысяч логических кубитов - таких отказоустойчивых машин пока нет.

FAQ

Чем поиск периода помогает разложить число? Из чётного периода $r$ функции $a^x \bmod N$ следует $a^r - 1 = (a^{r/2}-1)(a^{r/2}+1) \equiv 0 \pmod N$. Тогда $\gcd(a^{r/2} \pm 1, N)$ обычно дают нетривиальные делители - их считает классический алгоритм Евклида.

Почему именно квантовое преобразование Фурье? QFT за $O(t^2)$ вентилей переводит периодическую амплитудную структуру в пики на частотах, кратных $2^t/r$. Это позволяет считать период одним измерением, тогда как классическое БПФ потребовало бы экспоненциального числа операций.

Угрожает ли алгоритм Шора всем шифрам? Симметричным (AES) - нет, их лишь ослабляет Гровер. А вот RSA, схемы на эллиптических кривых и Диффи - Хеллман уязвимы, так как сводятся к факторизации или дискретному логарифму. Защита - переход на постквантовые алгоритмы.

Коротко

Алгоритм Шора факторизации сводит разложение числа $N$ к поиску периода $r$ функции $a^x \bmod N$: квантовый компьютер вычисляет её на суперпозиции всех аргументов, а квантовое преобразование Фурье выявляет период за $O(t^2)$ вентилей. Из чётного периода через $\gcd(a^{r/2}\pm 1, N)$ извлекаются множители - это уже классика. Итоговая сложность полиномиальна от $\log N$ против субэкспоненциального классического решета, что делает алгоритм экспоненциально быстрым и прямой угрозой RSA. На практике взлом упирается не в теорию, а в отсутствие отказоустойчивых квантовых машин нужного масштаба.