Алгоритм Шора

Каждый раз при открытии HTTPS-сайта браузер использует RSA или эллиптическую криптографию. Всё это шифрование держится на одном допущении: факторизация больших чисел слишком медленная. Алгоритм Шора разрушает это допущение. Именно поэтому правительства мира тратят миллиарды на постквантовую криптографию прямо сейчас.

• **NIST Post-Quantum Cryptography (2024)**: после 8 лет конкурса NIST стандартизировал CRYSTALS-Kyber и Dilithium. Google Chrome, Apple Safari, Cloudflare уже развёртывают поддержку.
• **NSA / АНБ**: в 2015 году объявило о переходе на post-quantum алгоритмы для государственных систем. «Harvest now, decrypt later» - реальная угроза для данных со сроком секретности 20+ лет.
• **IBM Quantum**: в 2023 году IBM запустила 1121-кубитный Condor. До квантовой угрозы RSA ещё далеко, но прогресс ускоряется - в 2033 году IBM планирует fault-tolerant машину.

Нахождение периода функции

Алгоритм Шора (1994) факторизует число N за полиномиальное время - задача, на которой держится безопасность RSA и большинства интернет-шифрования. Классически это занимает экспоненциальное время. Квантовое преимущество - в эффективном нахождении периода.

Ключевое наблюдение: факторизация N сводится к нахождению периода r функции `f(x) = a^x mod N`, где a - случайное число. Если период r найден и r чётный, то `НОД(a^(r/2) ± 1, N)` с высокой вероятностью даёт нетривиальный делитель N. Нахождение r классически требует O(N^(1/3)) операций, квантово - O((log N)^3).

Peter Shor разработал алгоритм в 1994 году. IBM в 2001 году реализовала его на 7-кубитном NMR-компьютере и факторизовала N=15. В 2023 году IBM факторизовала N=35 на реальном квантовом процессоре. Для угрозы RSA-2048 нужно ~4000 логических кубитов - пока недостижимо.

Quantum Fourier Transform в алгоритме Шора

QFT - квантовый аналог дискретного преобразования Фурье (DFT). Классический FFT на N точках требует O(N log N) операций. QFT на n кубитах (N=2^n точек) - O(n^2) квантовых гейтов. Разница: экспоненциальная, когда N >> n.

В алгоритме Шора QFT применяется к квантовому состоянию, содержащему суперпозицию значений f(x) = a^x mod N. Периодичность f(x) преобразуется в пики амплитуды на частотах, кратных 1/r. Измерение с высокой вероятностью даёт число, близкое к k/r, из которого можно восстановить r через continued fractions.

QFT на n кубитах требует n^2/2 квантовых гейтов. Для RSA-2048 (n=2048) это ~2M гейтов. С учётом коррекции ошибок и overhead - ~4000 физических кубитов с surface code. Текущие лучшие машины: IBM Eagle (127 кубитов), Google Sycamore (72 кубита) - на порядки меньше нужного.

Полная схема факторизации

Полная схема алгоритма Шора объединяет классические и квантовые вычисления. Квантовая часть занимает один шаг - нахождение периода. Всё остальное выполняется классически за полиномиальное время.

1. Классически: выбрать случайное a, проверить НОД(a,N). Если > 1 - делитель найден.
2. Квантово: подготовить суперпозицию |x> для x=0..2^n-1
3. Квантово: вычислить f(x) = a^x mod N через квантовые гейты
4. Квантово: применить QFT к регистру с f(x)
5. Классически: измерить, получить y ≈ k/r, восстановить r через continued fractions
6. Классически: вычислить НОД(a^(r/2)±1, N). Повторить если делитель тривиальный.

Квантовое возведение в степень (шаг 3) - самая дорогая часть: O(n^3) гейтов. Именно поэтому алгоритм Шора требует тысячи кубитов для больших чисел. Optimized реализации (2023) снизили требования до ~3000 кубитов для RSA-2048.

Угроза криптографии и постквантовая защита

RSA-2048 (основа HTTPS, TLS, SSH) держится на сложности факторизации 2048-битного числа. Классически: ~10^15 лет. Квантово с алгоритмом Шора: несколько часов при наличии fault-tolerant квантового компьютера с ~4000 логическими кубитами.

**«Harvest now, decrypt later»**: спецслужбы уже сейчас собирают зашифрованные данные. Когда квантовые компьютеры будут готовы (оценки: 10-20 лет), накопленные данные можно будет расшифровать. NIST в 2024 году стандартизировал первые post-quantum алгоритмы.

• **CRYSTALS-Kyber (ML-KEM)**: ключевой обмен на lattice-задачах, устойчивый к алгоритму Шора. Принят NIST 2024.
• **CRYSTALS-Dilithium (ML-DSA)**: цифровая подпись. Google Chrome уже включил поддержку.
• **SPHINCS+ (SLH-DSA)**: подписи на хэш-функциях - минимальные предположения о сложности.
• **Алгоритм Гровера**: квантово ускоряет перебор в 2x по длине ключа. AES-256 остаётся безопасным; AES-128 - под вопросом.

Ключевые идеи

• **Алгоритм Шора** сводит факторизацию к нахождению периода f(x) = a^x mod N, которое квантово решается через QFT за O((log N)^3).
• **QFT** преобразует периодичность квантового состояния в измеримые пики амплитуды за O(n^2) гейтов - против O(2^n) классически.
• **Угроза**: RSA-2048 требует ~4000 логических кубитов для взлома. Текущий уровень: ~100-1000 шумных физических. Горизонт: 10-20 лет.
• **Post-quantum**: NIST 2024 стандартизировал ML-KEM (Kyber) и ML-DSA (Dilithium) на lattice-задачах, устойчивых к алгоритму Шора.

Связанные темы

Алгоритм Шора связывает квантовые алгоритмы с реальной угрозой безопасности:

• Квантовое преобразование Фурье (QFT) — QFT - ключевой компонент алгоритма Шора; детальная схема и применения в phase estimation
• Квантовые ворота и схемы — Понимание Hadamard, controlled-phase и CNOT гейтов необходимо для построения QFT схемы

Вопросы для размышления

• Если квантовый компьютер с 4000 логическими кубитами появится в 2035 году, какие данные, зашифрованные сегодня, окажутся под угрозой?
• Алгоритм Гровера ускоряет поиск квадратично. Почему это не является экзистенциальной угрозой для симметричной криптографии (AES), в отличие от RSA?
• Post-quantum алгоритмы основаны на lattice-задачах. Что гарантирует, что завтра не появится классический алгоритм, решающий их эффективно?

Связанные уроки

• crypto-02-modular-arithmetic