Алгоритм Шора и угроза RSA

Главная причина тревоги криптографов: квантовая факторизация ломает RSA.

Алгоритм Шора разлагает большое число на множители за полиномиальное (по числу цифр) время, тогда как лучшие классические методы требуют субэкспоненциального.

Почему RSA держится на факторизации

Стойкость RSA опирается на простой факт: перемножить два больших простых числа легко, а разложить произведение обратно на множители — практически невозможно для классического компьютера, если числа достаточно большие (тысячи бит). Открытый ключ содержит произведение n = p·q; знание p и q даёт закрытый ключ. Вся защита держится на трудности факторизации. Если её взломать — RSA рушится.

Хитрость Шора: факторизация через период

Шор не «перебирает делители». Он сводит факторизацию к поиску периода функции f(x) = a^x mod n. Этот период r связан с множителями n через элементарную теорию чисел: зная r, множители находятся за пару строк классической арифметики (НОД). Поиск же периода — как раз то, что квантовый компьютер делает экспоненциально быстро с помощью квантового преобразования Фурье (оно «слышит» периодичность в фазах суперпозиции). Покажем классическую часть — как из найденного периода извлекают множители.

from math import gcd

def find_period(a, n):
    # классический поиск периода (медленно; квантовый делает это быстро)
    x, r = a % n, 1
    while x != 1:
        x = (x * a) % n
        r += 1
    return r

n = 15            # n = 3 * 5
a = 7             # случайное основание, взаимно простое с n
r = find_period(a, n)
print('период r =', r)
if r % 2 == 0:
    y = pow(a, r // 2, n)
    f1, f2 = gcd(y - 1, n), gcd(y + 1, n)
    print('множители:', f1, f2)

Вывод:

период r = 4
множители: 3 5

Период r=4 для 7^x mod 15, и через НОД сразу выпадают множители 3 и 5. Квантовая часть нужна именно для шага find_period на больших n, где классический перебор невозможен.

Как работает под капотом

Квантовое сердце Шора — квантовое преобразование Фурье (QFT). Суперпозиция значений a^x mod n содержит периодическую структуру, спрятанную в фазах амплитуд. QFT превращает эту скрытую периодичность в острые пики вероятности около кратных 1/r. Измерив, мы с большой вероятностью получаем дробь, из которой классически (цепные дроби) восстанавливаем r. Это тот же принцип, что и во всём курсе: записать ответ (период) в фазы, интерференцией собрать его в пики, измерить.

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

• «Шор уже сломал RSA». Пока нет: нужны тысячи логических (миллионы физических) кубитов с коррекцией ошибок, которых нет.
• Думать, что Шор перебирает делители. Он ищет период — это другая, быстрая задача.
• Считать, что под угрозой только RSA. Дискретный логарифм (а значит ECC, Диффи — Хеллман) Шор тоже ломает.

Итог

• Шор факторизует за полиномиальное время, сводя задачу к поиску периода.
• Квантовое преобразование Фурье извлекает период через интерференцию.
• Под угрозой RSA, ECC и Диффи — Хеллман; пока спасает отсутствие больших машин.