Квантові обчислення · Криптографія · Алгоритми
📅 Квітень 2026 ⏱ ≈ 13 хв читання 🎯 Просунутий · Останнє оновлення: 28 травня 2026 р.

Алгоритм Шора — як квантові обчислення зламують шифрування RSA

Алгоритм Шора, опублікований Пітером Шором 1994 року, був першим квантовим алгоритмом поліноміального часу для задачі, яка, як вважалося, потребує експоненційного класичного часу: факторизації цілих чисел. Факторизація n-бітного числа класично займає субекспоненційний час (найкраще: GNFS ~exp(n^(1/3))). Квантовий підхід Шора потребує O(n³) квантових вентилів, загрожуючи RSA-2048 та криптографії на еліптичних кривих. Він лишається одним із найважливіших алгоритмів в інформатиці.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. RSA і задача факторизації

Генерація ключів RSA: 1. Оберіть два великі прості числа p, q (кожне ~1024 біти для RSA-2048) 2. N = p × q (2048-бітний модуль, відкритий) 3. φ(N) = (p-1)(q-1) (функція Ейлера, закрита) 4. Оберіть відкритий показник e (зазвичай 65537) 5. Закритий ключ: d = e⁻¹ mod φ(N) Шифрування: C = Mᵉ mod N Розшифрування: M = Cᵈ mod N [працює, бо Mᵉᵈ ≡ M (mod N) за теоремою Ейлера] Безпека: щоб знайти d, противнику потрібен φ(N), що вимагає факторизації N = p×q. Складність класичної факторизації: пробне ділення: O(√N) = O(2^1024) — повністю неможливе. Квадратичне решето: L_N[1/2, 1] = exp(√(ln N · ln ln N)) GNFS (найкраще відоме): L_N[1/3, (64/9)^(1/3)] ≈ exp(N^(1/3)) Для RSA-2048: оцінка 10^23 операцій класично (>віку Всесвіту). Для алгоритму Шора: O(n³) = O(2048³) ≈ 10^10 квантових операцій.

2. Факторизація → знаходження періоду

Ключова ідея: факторизація N зводиться до знаходження ПОРЯДКУ (періоду) елемента в мультиплікативній групі Z*_N. Крок 1: оберіть випадкове a з 1 < a < N, gcd(a, N) = 1. (Якщо gcd(a,N) > 1, ми вже знайшли дільник — зроблено класично.) Крок 2: знайдіть ПОРЯДОК r = найменше додатне ціле, таке що: aʳ ≡ 1 (mod N) Послідовність 1, a, a², a³, ..., a^(r-1), 1, a, a², ... періодична з періодом r. Крок 3: якщо r парне і a^(r/2) ≢ -1 (mod N): факторизуємо через: gcd(a^(r/2) - 1, N) та gcd(a^(r/2) + 1, N) Бо: a^(r/2) ≡ 1 (mod N) → (a^(r/2) - 1)(a^(r/2) + 1) ≡ 0 (mod N) N ділить добуток, але N не є дільником жодного з членів окремо → НСД виділить нетривіальний дільник. Приклад: N=15, a=7 7¹=7, 7²=4, 7³=13, 7⁴=1 (mod 15) → r=4 a^(r/2) = 7² = 49 ≡ 4 (mod 15) gcd(4-1, 15) = gcd(3, 15) = 3 ✓ дільник знайдено! gcd(4+1, 15) = gcd(5, 15) = 5 ✓ інший дільник! Класичне знаходження періоду: O(√r) методом baby-step giant-step = усе ще експоненційне. Квантове знаходження періоду: O(n²) квантових вентилів — складну частину зроблено квантово.

3. Квантове перетворення Фур'є

Квантове перетворення Фур'є (QFT) — це квантовий аналог дискретного перетворення Фур'є, що діє на квантові стани замість класичних бітових рядків:

Класичне DFT: X_k = Σ_{j=0}^{N-1} x_j · e^{2πijk/N} QFT на обчислювальному базисі |j⟩: QFT|j⟩ = (1/√N) Σ_{k=0}^{N-1} e^{2πijk/N} |k⟩ Схема QFT (n кубітів, N=2ⁿ): використовує n вентилів Адамара та n(n-1)/2 вентилів контрольованого фазового повороту. Усього: O(n²) квантових вентилів проти O(n·2ⁿ) для класичного DFT на вході з 2ⁿ елементів. QFT використовує квантовий паралелізм: |j⟩ представляє конкретне число j, але застосовується в суперпозиції, щоб обробляти всі базисні стани одночасно. Ключова властивість: після застосування QFT до періодичної суперпозиції станів із періодом r результат має сильні амплітуди на кратних N/r. Це дає нам змогу зчитати r із результату вимірювання.

4. Квантова схема

Квантова підпрограма алгоритму Шора: Регістри: |0⟩_A |0⟩_B (A = керувальний, n+1 кубітів; B = цільовий, n кубітів) 1. Адамар на A: |0⟩_A → (1/√N) Σ_x |x⟩_A Створює рівномірну суперпозицію над усіма x із {0,...,N-1}. 2. Оракул модульного піднесення до степеня: |x⟩_A |0⟩_B → |x⟩_A |aˣ mod N⟩_B Цей унітарний оператор можна реалізувати за O(n³) квантових вентилів, використовуючи повторне піднесення до квадрата + квантову арифметику. 3. Стан після оракула: (1/√N) Σ_x |x⟩_A |aˣ mod N⟩_B Регістр B кодує періодичну функцію aˣ mod N. 4. Вимірюємо B: колапс до деякого значення v = aˢ mod N. Регістр A колапсує до суперпозиції всіх x з aˣ ≡ v (mod N): |A⟩ = (1/√(N/r)) Σ_k |s + kr⟩ (періодичний із періодом r, фаза s) 5. Застосовуємо квантове перетворення Фур'є до A. 6. Вимірюємо A: отримуємо значення c ≈ k·N/r для випадкового k. З c та N виділяємо r за допомогою ланцюгових дробів. Імовірність успіху за один запуск: ≥ 1/(2 ln r) ≈ 1/n Повторюємо O(n) разів → очікувано O(n) повторень, щоб знайти r.

5. Класична постобробка

Після вимірювання c ≈ k·(N/r) з виходу QFT: Мета: виділити r із відношення c/N. Метод: розклад c/N у ланцюговий дріб. Алгоритм ланцюгових дробів знаходить найкраще раціональне наближення p/q до c/N з q < N. Це дає q = r з високою ймовірністю. Алгоритм ланцюгових дробів: x₀ = c/N a₀ = ⌊x₀⌋ x₁ = 1/(x₀ - a₀) a₁ = ⌊x₁⌋ ... Підхідні дроби pₖ/qₖ: q₀=1, q₁=a₁, qₖ=aₖqₖ₋₁ + qₖ₋₂ Коли |c/N - k/r| < 1/(2N), підхідний дріб = k/r точно. Приклад: N=15, r=4, k=2, c ≈ 2×15/4 = 7.5 → c=7 або c=8 c/N = 7/15 = 0.4666... Ланцюговий дріб: [0; 2, 7] → підхідний дріб 7/15, але також [0; 2] = 1/2 1/2 → q=2, і 2|r=4 → період r=4 відновлено як 2q=4. Класична постобробка: O(n log n) зі швидкою цілочисловою арифметикою.

6. Вимоги до кубітів для RSA-2048

Факторизація n-бітного числа потребує: Логічні кубіти: ~2n + 3 = ~4099 логічних кубітів для RSA-2048 Квантові вентилі: O(n³) = O(2048³) ≈ 8.5 × 10⁹ вентилів Фізичні кубіти (з урахуванням виправлення помилок): поверхневий код: ~1000 фізичних кубітів на один логічний кубіт Фізичні кубіти для RSA-2048: ~4 МІЛЬЙОНИ фізичних кубітів! Поточний стан (2024): Google Willow: 105 фізичних кубітів, ~99.7% точність двокубітних вентилів IBM Quantum Condor: 1121 фізичний кубіт (важка гексагональна ґратка) Поріг відмовостійкості: усе ще за роки до криптографічного масштабу Найкращий класичний рекорд факторизації: RSA-250 (829 бітів) факторизовано 2020 року: ~2700 CPU ядро-років. RSA-2048 (2048 бітів): оцінка > 10^23 операцій. Оптимістичні строки для квантової факторизації RSA-2048: Консервативна оцінка: 2030–2040 для демонстрації на малих розмірах ключа Великомасштабна атака: 2030-ті–2050+ залежно від прогресу обладнання Атаки «зберігай зараз, розшифруй пізніше»: противники збирають зашифровані дані сьогодні, щоб розшифрувати, щойно з'являться квантові комп'ютери → нагальність переходу на PQC.

7. Постквантова криптографія

NIST стандартизував постквантові криптографічні алгоритми 2024 року (після понад 6 років оцінювання):

Гібридне впровадження (рекомендоване на 2024–2030): використовуйте класичний TLS 1.3 + постквантовий KEM одночасно (X25519+ML-KEM-768). Класичний алгоритм захищає від поточних атак; PQC захищає від «зберігай зараз — розшифруй пізніше». І Google Chrome, і Cloudflare впровадили гібридний TLS до 2024 року.
⚛️ Досліджуйте квантову фізику →