ЄМНІСНА СКЛАДНІСТЬ ВИЗНАЧЕННЯ НСД В АЛГОРИТМІ ШОРА

Анотація

У статті проаналізовано результати пошуку періоду r функції y = axmodM (a - випадкове число), яка використовується в алгоритмі факторизації Шора для квантових комп'ютерів. Модуль M є добутком двох простих чисел p і q. У статті проаналізовано розв'язки r, отримані для різних a, для яких ємнісна складність H знаходження найбільшого спільного дільника НСД(ar/2 + 1, M) є найменшою. Цифровий квантовий комп'ютер - це класичний процесор та його цифровий квантовий копроцесор. Цифровий квантовий копроцесор з сотнями і тисячами цифрових кубітів може бути реалізований в одній програмованій логічній інтегральній схемі ПЛІС. В алгоритмі Шора задача факторизації числа M зводиться до задачі визначення періоду r функції y. Відомо, що НСД(ar/2 + 1, M) може бути дільником числа M.  Завданням квантового копроцесора при реалізації алгоритму Шора є пошук періоду r. Після
цього необхідно знайти НСД. Оскільки для випадкового a проблема пошуку періоду r має багато
рішень, ці рішення можна порівняти за значенням одного з аргументів при знаходженні НСД –
числа a r/2. При цьому аналізується H = (rlog2a)/2. Він приблизно представляє розрядність двійкових
кодів, які класичний комп'ютер повинен буде обробляти при визначенні НСД.  H може змінюватися в широкому діапазоні від десятків до тисяч біт навіть при малих значеннях M. У цьому дослідженні період r, який забезпечує найменшу складність подальшого завдання пошуку НСД, найчастіше є рішенням для a = 3 і a = 2, але він може часто траплятися і для інших значеннь a. Для уточнення виявлених закономірностей, особливо для великих М, необхідно провести додаткові дослідження.