Алгоритм Шора розкладає великі цілі числа на множники експоненційно швидше за будь-який відомий класичний метод, знаходячи період r функції aˣ mod N для випадкової основи a, взаємно простої з N. Квантовий комп'ютер знаходить цей період за допомогою квантової оцінки фази (QPE), а потім короткий класичний обчислювальний крок за алгоритмом Евкліда перетворює r на справжні множники N. Оскільки RSA та подібні криптосистеми з відкритим ключем спираються на складність факторизації, достатньо потужний квантовий комп'ютер, що виконує цей алгоритм, зламав би їх — саме тому сьогодні активно впроваджують постквантову криптографію.
Чесне застереження: моделювання реальної схеми QPE вимагає багатьох кубітів і є занадто важким для canvas у браузері. Ця демонстрація точно відтворює класичну послідовність пошуку періоду, а потім малює спрощений, ілюстративний «спектр» із піками на фазах k/r, які дав би реальний квантовий вимір — це навчальний інструмент, а не змодельована квантова схема.
aʳ ≡ 1 (mod N) — r є мультиплікативним порядком a за
модулем N. Коли r парне і a^(r/2) ≢ −1 (mod N), вирази
gcd(a^(r/2) − 1, N) та
gcd(a^(r/2) + 1, N) дають нетривіальні множники N.
Пітер Шор опублікував цей алгоритм у 1994 році, вперше показавши, що квантові комп'ютери можуть розв'язувати практично важливу задачу експоненційно швидше за будь-який відомий класичний алгоритм. Невеликі демонстрації — розкладання таких чисел, як 15 і 21 — виконувалися на реальному фізичному квантовому обладнанні ще з початку 2000-х років, хоча масштабування до криптографічно значущих розмірів залишається серйозним інженерним викликом.
Алгоритм Шора, опублікований математиком Пітером Шором у 1994 році, — це результат, який перетворив квантові обчислення з теоретичної цікавинки на екзистенційне питання для сучасної криптографії. Він розкладає складене число N на множники, знаходячи період r послідовності aˣ mod N для деякої основи a, взаємно простої з N — задачу, яку квантовий комп'ютер може виконати експоненційно швидше за будь-який відомий класичний метод, використовуючи операцію під назвою квантова оцінка фази (QPE), щоб зчитати r безпосередньо з інтерференційних картин у суперпозиції станів. Щойно r відомий, коротке обчислення за алгоритмом Евкліда, застосоване до ar/2 ± 1 та N, дуже часто виявляє два справжні, нетривіальні множники N.
Це має значення далеко за межами чистої математики: криптосистема з відкритим ключем RSA, яка й досі захищає значну частку інтернет-трафіку, банківських операцій та безпечних комунікацій, повністю спирається на припущення, що факторизація великих чисел обчислювально нездійсненна. Достатньо великий, стійкий до похибок квантовий комп'ютер, що виконує алгоритм Шора, зруйнував би це припущення — саме тому уряди та органи стандартизації вже впроваджують постквантову криптографію, розроблену для протидії квантовим атакам. Цей симулятор проводить через класичну послідовність пошуку періоду, ілюстративне відтворення квантового спектра, який виміряв би QPE, і реальну арифметику алгоритму Евкліда, що перетворює період на факторизацію — на невеликих, перевірюваних вручну прикладах N = 15, 21 і 35.
Він розкладає складене число N на прості множники. Класично найкращі відомі алгоритми факторизації великих чисел працюють за час, що зростає майже експоненційно з кількістю цифр, тому шифрування RSA, засноване на складності факторизації, залишалося безпечним десятиліттями. Алгоритм Шора розкладає N за час, що зростає лише поліноміально — експоненційне пришвидшення для достатньо великих N.
Якщо a взаємно просте з N, а r парне і ar/2 не конгруентне −1 за модулем N, то ar/2 − 1 та ar/2 + 1 є свідченнями того, що N ділить їхній добуток, але не кожен множник окремо. Алгоритм Евкліда, застосований до gcd(ar/2 − 1, N) та gcd(ar/2 + 1, N), тоді виділяє справжній нетривіальний множник N безпосередньо з цього арифметичного факту.
Ні, і ця сторінка прямо про це говорить. Моделювання реальної схеми квантової оцінки фази, яка знаходить r, вимагало б моделювання багатьох кубітів, що набагато перевищує можливості canvas у браузері. Натомість ця демонстрація обчислює r класично за допомогою звичайного циклу, а потім малює ілюстративний «спектр» із піками на k/r, щоб у навчальних цілях показати, як виглядав би реальний вимір QPE.
Побудова через gcd працює лише тоді, коли період r парний, а ar/2 не конгруентне −1 за модулем N. Якщо r виявляється непарним, або якщо обчислення gcd повертає лише тривіальні множники 1 чи N, обрана основа a просто не підходить для цього методу. Стандартне рішення, як тут, так і в реальному алгоритмі, — спробувати іншу випадкову основу a і повторити.