Алгоритм Шорса: Факторизація шляхом пошуку періоду

Факторизація складна, але пошук періоду – справжня мета

Помножити два великі прості числа разом легко обчислити; рухаючись у зворотньому напрямку, знайти два прості числа, маючи лише їхній добуток, як було доведено багатьма, є експоненціально важким для класичного комп’ютера, коли числа зростають. Алгоритм Петра Шора 1994 року не атакує факторизацію безпосередньо. Він робить обхідний шлях через зовсім іншу проблему – пошук періоду періодичної послідовності – вирішує цю проблему експоненціально швидше на квантовому комп’ютері, а потім завершує роботу з використанням звичайних класичних обчислень.

Від розкладання N на період a^x mod N

Щоб розкласти непарне складене число N (яке не є степенем простого числа), виберіть випадкове ціле число a між 1 і N, де gcd(a, N) = 1. Послідовність a¹ mod N, a² mod N, a³ mod N,... гарантовано періодична - вона рано чи пізно повториться, оскільки є лише N можливих залишків - і її період r називається теорією чисел мультиплікативним порядком a modulo N:

a^x mod N періодичне в x з деяким періодом r, a^r ≡ 1 (mod N) якщо r є ДІЄМНИМ і a^(r/2) ≠ -1 (mod N): p = gcd( a^(r/2) - 1 , N ) q = gcd( a^(r/2) + 1 , N ) з великою ймовірністю, p і q є нетривіальними множниками N Алгебра за останнім кроком звичайна: якщо r є парним, то a^(r/2) є нетривіальним квадратним коренем 1 modulo N, і N | (a^(r/2)-1)(a^(r/2)+1) без того, що N ділить один із цих факторів окремо - що обчислення gcd алгоритмом Евкліда виявляє безпосередньо, за поліноміальний час, коли r відомий. Близько половини випадково обраних a дають корисний r з першого разу, і перекидання іншого a, коли вони не роблять цього, є дешевим, тому вся задача розкладання дійсно спрощується до одного питання: швидко знайти r.

a^x mod N  is periodic in x with some period r,   a^r ≡ 1 (mod N)

if r is EVEN and a^(r/2) ≢ -1 (mod N):
    p = gcd( a^(r/2) - 1 ,  N )
    q = gcd( a^(r/2) + 1 ,  N )
    with high probability, p and q are non-trivial factors of N

Чому класичне пошукове періодизування застрягло

Класичний пошук r означає обчислення a^x mod N для достатньої кількості значень x, щоб помітити повторення - і для n-бітного N, r може бути експоненціально великим у n, тому грубий пошук безвихідного. Немає відомих класичних алгоритмів, які знаходять r швидше, ніж час з під-експонентою (загальний сорт снігової бульки атакує розкладання безпосередньо, з подібною вартістю під-експоненти), що є точною прогалиною, яку використовує алгоритм Шора, переміщуючи пошук у квантовий регістр, який може представляти кожне значення x одночасно.

Квантова частина: суперпозиція, потім перетворення

1. Завантажити реєстр 1 з рівновірнійною суперопозицією над x = 0 .. 2^t - 1 2. Обчислити a^x mod N у реєстр 2 (зв’язати два реєстри) 3. Застосувати Квантовий Фур'є Перетворення до реєстру 1 4. Виміряти реєстр 1 → результат близький до кратного 2^t / r 5. Класичний розширення з числами нескінченності дробу для (результат / 2^t) виявляє r

Крок 2 вводить весь періодичний функціонал a^x mod N у суперпозицію одним кроком, використовуючи модульне піднесення до степеня, побудоване з зворотних арифметичних схем. Оскільки ця функція повторюється з періодом r, шаблон амплітуд реєстру 1 - після зв’язку з реєстром 2 - успадковує той самий період. Квантове Фур'є Перетворення (див. нашу супутню статтю про QFT) є саме інструментом, побудованим для перетворення періодичності в одній базі в гострі піки в іншій: воно концентрує ймовірність вимірювання на результатах, близьких до цілих кратних 2^t/r, а числа нескінченності - це чисто класична, столітня техніка - витягують точну дріб 2^t/r, отже r, з цього одного шумного вимірювання з високою ймовірністю. Якщо спроба зазнає невдачі (r виявляється непарним або дає тривіальний множник), весь процес просто повторюється з новим випадковим a - на середньому достатньо кількох спроб з малим константом.

1. load register 1 with an equal superposition over x = 0 .. 2^t - 1
2. compute a^x mod N into register 2 (entangling the two registers)
3. apply the Quantum Fourier Transform to register 1
4. measure register 1 → result is close to a multiple of 2^t / r
5. classical continued-fraction expansion of (result / 2^t) reveals r

Чому RSA має значення

Шифрування RSA базує свою безпеку на безпосередній ставці, що розкладання добутку двох великих простих чисел є класично неможливим. Алгоритм Шора працює за поліноміального часу від кількості біт N - кілька тисяч квантових гейтів на декілька тисяч логічних, виправлених помилками кубітів для ключа RSA 2048 біт, за оцінками, що робить цю ставку недійсною. Будівництво квантового комп’ютера з достатньою кількістю чистих, виправлених помилок кубітів для запуску алгоритму Шора на криптографічно значущих числах залишається складною інженерною задачею, яка не вирішена сьогодні, але існування алгоритму саме тому спонукає криптографічну спільноту протягом останнього десятиліття стандартизувати алгоритми після квантового періоду - схеми, засновані на проблемах з решітками та інших структурах, які вважаються стійкими як до класичних, так і до квантових атак - для заміни RSA та еліптичної криптографії до прибуття достатньо потужного квантового комп’ютера.

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

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

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