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

Чому RSA довіряє розкладанню на множники

RSA шифрування ґрунтується на одній асиметрії: множення двох великих простих чисел відбувається швидко, але відновлення цих простих чисел з їхнього добутку є, за твердженням будь-кого, надзвичайно повільним класично. Згенеруйте два великі прості числа p і q, опублікуйте їхній добуток N = p·q як модуль та тримайте p і q у секреті. Приватний ключ виводиться з φ(N) = (p−1)(q−1), який не може обчислити будь-хто, хто знаходиться зовні ключового зберігача, без спочатку розкладання N. Алгоритм Петра Шора 1994 року був першим поліноміальним алгоритмом — квантовим чи класичним — для цієї конкретної проблеми, і саме тому RSA-2048 та еліптична криптографія вважаються вразливими відносно достатньо потужного квантового комп'ютера.

Найкраще класичне розкладання (GNFS): час ≈ exp(N^(1/3)) для RSA-2048: ~10²³ операцій Алгоритм Шора: час ≈ O(n³) кубітів квантових обчислень для RSA-2048: ~10¹⁰ операцій Ця десятикратна різниця у масштабуванні між експоненціальним і поліноміальним — не швидший перебір, а структурно інший алгоритм — робить Алгоритм Шора таким знаковим, і тому моделювання навіть невеликої його інстанції, як інтерактивна демонстрація на цьому сайті, варте зробити вручну.

best classical factoring (GNFS):  time ≈ exp(N^(1/3))         for RSA-2048: ~10²³ operations
Shor's algorithm:                 time ≈ O(n³) quantum gates    for RSA-2048: ~10¹⁰ operations

Зменшення: розкладання - це пошук періоду в маскерлані

Реальний провидницький момент Шора полягав не у швидшому способі безпосереднього пошуку множників — а в усвідомленні, що розкладання N зменшується до пошуку порядку випадкового елемента в мультипликативній групі відносно N. Виберіть випадковий a з 1 < a < N і gcd(a,N) = 1 (якщо gcd не дорівнює 1, ви вже натрапили на множник класично, без необхідності квантового комп’ютера). Послідовність a¹, a², a³, ... відносно N періодична; назвемо її період r — найменше додатне ціле число, таке що aʳ ≡ 1 (mod N). Якщо r випадково парний і a^(r/2) не конгруентний -1 (mod N), елементарна алгебра надає вам множник безкоштовно.

a^(r/2) ≡ 1 (mod N) ⟹ (a^(r/2) − 1)(a^(r/2) + 1) ≡ 0 (mod N)

a^(r/2) ≡ 1 (mod N)  ⟹  (a^(r/2) − 1)(a^(r/2) + 1) ≡ 0 (mod N)

worked example:  N = 15, a = 7
  7¹=7, 7²=4, 7³=13, 7⁴=1 (mod 15)  →  order r = 4
  a^(r/2) = 7² = 49 ≡ 4 (mod 15)
  gcd(4−1, 15) = gcd(3, 15) = 3      ✓ factor found
  gcd(4+1, 15) = gcd(5, 15) = 5      ✓ other factor found

Квантова перетворення Фуріє читає період

Квантове перетворення Фуріє (QFT) є квантовим родичем дискретного перетворення Фуріє: воно перетворює амплітуди суперпозиції квантових базових станів, а не список класичних чисел. На n кубітах потрібно лише n гейтів Хадінгарда та n(n−1)/2 обертань з контрольованим фазовим зміщенням — загалом O(n²) гейтів, порівняно з O(n·2ⁿ) для класичного DFT у цьому ж просторі з 2ⁿ елементами. Властивість, яка робить це корисним тут: подайте QFT суперпозицію, амплітуди якої періодичні з періодом r, і вихідні амплітуди зосередяться гостро біля кратних N/r, що може бути виявлено за допомогою вимірювання.

Підрозділ Шорта виконує це, використовуючи дві реєстри. Контрольна регістра переводиться в рівномірну суперпозицію для кожного значення x від 0 до N−1 з використанням n гейтів Хадінгарда. Модульний експоненційний пристрій потім обчислює aˣ mod N у цільову реєстр — для кожного x у суперпозиції одночасно, завдяки квантовій паралелізації — використовуючи O(n³) гейти, побудовані з повторного піднесення до квадрату. Вимірювання цільової реєстру призводить до колапсу в одне значення, яке, в свою чергу, призводить до колапсу контрольної реєстри в суперпозицію точно тих значень x, які виробляють це значення: стан періодичний щодо x з періодом r. Застосовуйте QFT до цього періодичного суперпозиції та вимірюйте ще раз, і результат c дуже ймовірно буде близький до деякого цілого кратника N/r.

Від зашумленого вимірювання до точного періоду

QFT повертає наближення, c ≈ k·N/r для деякого невідомого цілого числа k — не r саме. Відновлення точного періоду з c/N є класичною проблемою, вирішеною за допомогою розширення удовсвідної дробу: записуючи c/N як удовсвідну дріб та читаючи звідти його збіжність p/q, ми отримуємо найкращі раціональні наближення до c/N з малими знаменниками, і коли |c/N − k/r| < 1/(2N), одна з цих збіжностей точно дорівнює k/r, розкриваючи r (або невеликому множнику, який перевірка вище вирішує).

Які кубіти дійсно потрібні RSA-2048

Факторизація числа з n бітами потребує порядку 2n + 3 логічних кубітів — приблизно 4000 для модуля RSA-2048 (2048 біт) — що виконується приблизно 10¹⁰ квантових гейтів. Відстань між логічними та фізичними кубітами саме там, де ховається справна складність: корекція помилок поверхневого коду, основної схемі стійкості, потребує порядку 1000 шумів фізичних кубітів на чистий логічний кубіт, що становить приблизно 4 мільйони фізичних кубітів для RSA-2048. Найбільші процесори, побудовані станом на 2026 рік, працюють у тисянях фізичних кубітів — серед яких Willow від Google та Condor-клас від IBM, тому факторизація, що має значення для криптографії, залишається проблемою обладнання, вимірюваною роками чи десятиліттями, а не проблемою програмного забезпечення, яка чекає на кращий алгоритм.

Чому відбувається міграція до постквантової криптографії зараз взагалі

Відстань до функціонального великого квантового комп’ютера саме тому, організації не чекають, поки він буде побудований. Закодований трафік, захоплений сьогодні, може бути просто збережений і розшифрований пізніше, коли обладнання існує — атака "збирай зараз, розшифруй пізніше", яка загрожує лише даними, які все ще потребують конфіденційності через роки. NIST завершив свої перші стандарти постквантової криптографії у 2024 році після шестирічної публічної оцінки: ML-KEM (раніше CRYSTALS-Kyber) для обміну ключами, ML-DSA (раніше Dilithium) для підписів, а також SLH-DSA та FN-DSA як альтернативи, побудовані на різних важких задачах. Обидва покладаються на проблеми з лабіринтами або хешами, які вважаються стійкими до квантового нападу, на відміну від проблеми факторизації RSA. Великі браузери та CDN-провайдери вже розгорнули гібридні схеми, які запускають класичний алгоритм і постквантовий біля одного з них сьогодні, щоб сьогоднішні з’єднання залишалися захищеними, навіть якщо один із двох підходів буде зламаний зрештою.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.