Ця симуляція проходить крізь алгоритм Шора крок за кроком для малих чисел, які неможливо було б зламати так на справжньому квантовому комп'ютері, але тут можна спостерігати покроково: оберіть основу a, взаємно просту з N, обчисліть послідовність aˣ mod N, знайдіть її період r (єдиний крок, який справжній квантовий комп'ютер прискорює через QFT), потім візьміть gcd(a^(r/2)±1, N), щоб видобути прості множники N. Спробуйте різні значення N та a, щоб побачити, коли метод спрацьовує чисто, а коли потребує повтору.
Стовпчикова діаграма aˣ mod N, що виявляє повторюваний період r, і симульований квантовий регістр, що показує піки ймовірності, зосереджені на кратних Q/r після квантового перетворення Фур'є — результат вимірювання, що дозволяє видобути r.
Оберіть N для факторизації і основу a, або натисніть Random a для автовибору ймовірно успішного значення, потім проходьте чотири етапи кнопкою Next stage або дивіться їх усі одразу через Run all stages, або оберіть пресет (N=15, 21, 35, 91), щоб побачити gcd, період r, піки QFT і кінцеві множники.
Алгоритм Шора не факторизує N безпосередньо — його єдиний по-справжньому квантовий крок полягає у знаходженні періоду r для aˣ mod N експоненційно швидше за будь-який відомий класичний метод; все інше (вибір a, обчислення gcd) — звичайна класична арифметика, саме тому він загрожує шифруванню RSA.
Це найменше додатне ціле r таке, що aʳ mod N = 1. Оскільки aˣ mod N циклічно повторюється з періодом r, знаючи r, можна алгебраїчно видобути множники N — ця симуляція виділяє цей повторюваний цикл прямо на стовпчиковій діаграмі.
Знаходження періоду aˣ mod N класично вимагає перевірки значень одне за одним, що стає експоненційно повільним для великих N. Квантовий комп'ютер може підготувати суперпозицію одразу над усіма x і використати QFT, щоб результати вимірювання зосередились на кратних Q/r, розкриваючи r за набагато менше кроків.
Якщо період r виявляється непарним, або a^(r/2) ≡ −1 (mod N), крок gcd не може видобути нетривіальний множник з цього конкретного вибору a — виправлення просто в тому, щоб обрати інше a і спробувати знову, тому кнопка "Random a" шукає значення, ймовірно успішне.
Безпека RSA спирається на обчислювальну нездійсненність факторизації великого добутку двох простих чисел, що використовується як публічний ключ. Алгоритм Шора факторизує цілі числа експоненційно швидше за найкращі відомі класичні алгоритми, тож достатньо великий квантовий комп'ютер міг би зламати нинішні безпечні ключі RSA.
Коли r парне і a^(r/2) не congruent −1 mod N, тотожність (a^(r/2)−1)(a^(r/2)+1) ≡ 0 (mod N) означає, що N має спільний нетривіальний множник хоча б з одним із цих двох членів — обчислення gcd з кожним видобуває цей спільний множник напряму.