44 якщо β𝑎
𝑗
відповідає якомусь значенню i. Таким чином знаходяться індекси i і j, які задовольняють співвідношенню (1) і дозволяють обчислити значення x = i ⋅ m – j.
 алгоритм Менезеса-Окамото-Ванстона.
Ідея алгоритму полягає в переході від проблеми дискретного логарифму на еліптичній кривій E(𝐹
𝑞
) до проблеми дискретного логарифму в 𝐹
𝑞
𝑚
𝑥
для деяких m.
Після цього переходу, проблема може бути вирішена досить швидко, використовуючи атака обчислення індексу, якщо m - не велике. Невеликі m завжди можуть бути отримані для певних типів кривих. Почнемо з визначення групування Вейля для кривих E(𝐹
𝑞
).
 ρo-алгоритм Полларда для дискретного логарифму [17]
Алгоритм Полларда є імовірнісним алгоритмом, що дозволяє знаходити дискретний логарифм виду Q = xP, де 0 < 𝑥 < 𝑛, 𝑛 − порядок групи, і працює зі складністю, що залежить лише від величини модуля. Примітний також тим, що існує варіант реалізації такого алгоритму, який має більш складну ітераційну функцію, яка призводить до пришвидшення алгоритму;
 алгоритм Поліґа-Геллмана [18]
Спеціалізований алгоритм, який отримує перевагу від факторизації порядку 𝑛 мультиплікативної групи порядку G , де 𝑛 – гладке число, нехай 𝑛 = 𝑝
1
𝑒
1
𝑝
2
𝑒
2
… 𝑝
𝑟
𝑒
𝑟
, буде розкладом на прості множники. Якщо 𝑥 = log
𝛼
𝛽, тоді підхід до вирішення задачі полягає в знаходженні 𝑥
𝑖
= 𝑥 𝑚𝑜𝑑 𝑝
𝑖
𝑒
𝑖
, для 1 ≤ 𝑖 ≤ 𝑟 і подальшому розрахунку 𝑥.
Кожен з 𝑥
𝑖
визначається обчисленням
𝑙
0
,
𝑙
1
, … , 𝑙
𝑒
𝑖
−1
для його
𝑝
𝑖
− арного представлення 𝑥
𝑖
= 𝑙
0
+ 𝑙
1
𝑝
𝑖
+ ⋯ + 𝑙
𝑒
𝑖
−1
𝑝
𝑒
𝑖
−1
, де
0 ≤ 𝑙
𝑗
≤ 𝑝
𝑖
− 1.
Передбачувана велика обчислювальна складність завдання пошуку дискретного логарифму лежить в основі крипостійкості деяких алгоритмів шифрування з відкритим ключем, таких як ECDH та ECDSA.

45 3.2 Алгоритм пошуку дискретного логарифму Шора та його варіації.
Дискретний алгоритм Шора [19][20] – квантовий алгоритм пошуку дискретного логарифму, квантова реалізація якого, дозволяє знайти дискретний логарифм у групі з порядком n бітів за час O(n
3
), використовуючи O(6n) логічних кубітів. Алгоритм був розроблений Пітером Шором у 1994 році.
Обидва алгоритма Шора (для факторизації та дискретного логарифму) пізніше почали розглядатися, як спеціальні випадки більш загального фреймворку, який називається проблема схованої абеліанівської підгрупи. В той час, як в алгоритмі факторизації розглядається підгрупа групи цілих чисел Z, у випадку дискретного логарифму розглядається підгрупа 𝑍
2
. Зокрема, просторова підрешітка решітки 𝑍
2
, така, що її елементи можуть бути записані як лінійна комбінація двох (лінійно не залежних) векторів в 𝑍
2
. Таким чином, алгоритм для дискретного логарифму можна розглядати, як двовимірну версію алгоритму факторизації.
Для алгоритму дискретного логарифма над еліптичними кривими, перш за все робиться припущення, що період базової точки 𝛼 еліптичної кривої – це просте число
і воно відоме до початку роботи алгоритму. Якщо період 𝛼 не відомий, то його можна знайти за допомогою алгоритму пошуку періоду, що використовується в алгоритму факторизації. У таблиці 1.2 наведено приклад періодичної функції на еліптичній кривій для базової точки 𝛼.
Таблиця 3.1 – Значення періодичної функції для різних n (n 𝛼) на кривій y
2
= x
3
+ 2x + 2 (mod 17) з початковою точкою
𝛼 = (5,1) n
1 2
3 4
5 6
7 8 n
𝛼
mod p n(5,1)
mod 17
(5,1) (6,3) (10,6) (3.1) (9,16) (16,13) (0,6)
(13,7)

46
Кінець таблиці 3.1 n
9 10 11 12 13 14 15 16 n
𝛼
mod p n(5,1)
mod 17
(7,6)
(7,11) (13,10) (0,11) (16,4) (9,1) (3,16) (10,11) n
17 18 19 20 21 n
𝛼
mod p n(5,1)
mod 17
(6,14)
(5,16)
(0,0)
(5,1)
(6,3)
Алгоритм пошуку дискретного логарифма полягає в наступному: нехай задано
𝛼
𝑞
= 𝑒, де q – просте число і 𝛽 = 𝛼
𝑑
, де d – не відоме і знаходиться у проміжку від 0 до q – 1. Розглянемо функцію 𝑓(𝑥, 𝑦) = 𝛼
𝑥
𝛽
𝑦
для цілих чисел x та y. Ця функція має два незалежні періоди на площині 𝑍
2
, що видно з функції 3.1.
𝑓(𝑥 + 𝑞, 𝑦) = 𝑓(𝑥, 𝑦)та 𝑓(𝑥 + 𝑑, 𝑦 − 1) = 𝑓(𝑥, 𝑦)
(3.1)
Таким чином усі x, y разом з 𝑓(𝑥, 𝑦) = 𝑒 формують просторову підрешітку від
𝑍
2
Двовимірне перетворення Фур’є приводить до подвійної решітки з якої можна визначити d. Треба зауважити, що 𝑓(𝑥, 𝑦) можна роздивлятися, як функцію визначену над 𝑍
𝑞
2
, як
𝑓(𝑥, 𝑦) = 𝑓(𝑥 𝑚𝑜𝑑 𝑞, 𝑦 𝑚𝑜𝑑 𝑞).
Далі, спочатку уявимо, що нам відомий спосіб виконати квантове швидке перетворення Фур’є з періодом q (𝑄𝐹𝐹𝑇
𝑞
), тому, що у цьому випадку алгоритм міг би виглядати краще.
Тоді алгоритм починається з наступного стану двох квантових регістрів, з яких, за допомогою «квантового паралелізму» вираховується 𝛼
𝑥
𝛽
𝑦
як видно з формули
(3.2).

47 1
𝑞
∑ ∑ |𝑥, 𝑦 >
𝑞−1
𝑦=0
𝑞−1
𝑥=0
→
1
𝑞
∑ ∑ |𝑥, 𝑦, 𝛼
𝑥
𝛽
𝑦
>
𝑞−1
𝑦=0
𝑞−1
𝑥=0
(3.2)
Знову уявимо, що ми зараз виміряємо значення останнього регістра. У такому разі ми отримаємо випадковий елемент 𝛼
𝑥
0
з групи згенерованої
𝛼, при цьому значення 𝑥
0
знаходиться у проміжку від 0 до q – 1. Тоді необхідно знайти два перші регістри у суперпозиції всіх x, за формулою (3.3).
𝛼
𝑥
𝛽
𝑦
= 𝛼
𝑥
( 𝛼
𝑑
)
𝑦
= 𝛼
𝑥
0
(3.3)
Так як період 𝛼 це q, цей вираз еквівалентний формулі (3.4).
𝑥 + 𝑑𝑦 ≡ 𝑥
0
(𝑚𝑜𝑑 𝑞), або 𝑥 = (𝑥
0
− 𝑑𝑦) 𝑚𝑜𝑑 𝑞
(3.4)
Тож для y існує тільки одне рішення і стан двох перших регістрів наступний відображено у формулі (3.5).
1
√𝑞
∑ |𝑥
0
− 𝑑𝑦, 𝑦 >
𝑞−1
𝑦=0
(3.5)
Тепер варто виконати перетворення Фур’є над кожним з двох регістрів використовуючи наше (гіпотетичне) квантове перетворення Фур’є періоду q, яке діє на базові стани згідно з формулою (3.6).
|
𝑧 > →
1
√𝑞
∑
|𝜔
𝑞
𝑧𝑧̇
, 𝑧̇ >
𝑞−1
𝑧̇=0
,
(3.6) де
𝜔
𝑞
= 𝑒
2𝜋𝑖 𝑞
⁄

48
Після перетворення формули (3.6) ми отримаємо формулу (3.7).
1
√𝑞
1
𝑞
∑ ∑ 𝜔
𝑞
(𝑥
0
−𝑑𝑦)𝑥̇
𝜔
𝑞
𝑦𝑦̇
|𝑥̇, 𝑦̇ >
𝑞−1
𝑦=0
𝑞−1
𝑦̇=0
(3.7)
Тепер можна розрахувати суму по y. Вона дорівнює 𝑞𝜔
𝑞
𝑥
0
𝑥
0
̇
, якщо
𝑞𝜔
𝑞
𝑥
0
𝑥
0
̇
і зводиться до 0 у іншому випадку. Таким чином, після розрахунку, ми отримаємо формулу (3.8).
1
√𝑞
∑ 𝜔
𝑞
𝑥
0
𝑥̇
|𝑥̇, 𝑦̇ = 𝑑𝑥̇ 𝑚𝑜𝑑 𝑞 >
𝑞−1
𝑥̇=0
(3.8)
Тепер можна побачити, що вірогідність виміру базового стану не залежить від
𝑥
0
, і тому не має значення яке
𝑥
0
ми виміряли вище. Після вимірювання ми отримуємо пару 𝑥̇, 𝑦̇, з якої ми можемо розрахувати 𝑑 = 𝑦̇(𝑥)̇
−1
𝑚𝑜𝑑 𝑞, якщо 𝑥̇ ≠ 0.
На практиці нам необхідно замінити кожне 𝑄𝐹𝐹𝑇
𝑞
на швидке квантове перетворення Фур’є з періодом 2
𝑛
(𝑄𝐹𝐹𝑇
2
𝑛
) , тому що його можна фінітно реалізувати. Для розглянутого вище 𝑄𝐹𝐹𝑇
𝑞
, ми завжди можемо отримати пару
𝑥̇, 𝑦̇ з
𝑦̇ ≡ 𝑑𝑥̇ 𝑚𝑜𝑑 𝑞 при фінальному вимірі. Однак для 𝑄𝐹𝐹𝑇
2
𝑛
ми отримаємо велику вірогідність виміряти пару 𝑥̇, 𝑦̇, якщо умова у формулі (3.9) виконується.
(
𝑥̇𝑞
2
𝑛
,
𝑦̇𝑞
2
𝑛
) ≈ (𝑘, 𝑑𝑘),
(3.9) де k – деяке ціле число
Для 2
𝑛
≈ 𝑞 ми маємо хорошу (константну) вірогідність отримати правильні значення в 𝑍
𝑞
2
після округлення.

49
Окрім алгоритму Шора над простим полем Ϝ
𝑝
∗
існують різні модифікації алгоритму для пошуку дискретного логарифму в особливих випадках, або ж над
іншими скінченними групами. Як приклад такого алгоритму можна привести алгоритм для розрахунку дискретного логарифму 𝑑 у групі Ϝ
𝑝
∗
для випадку де
𝑑 ⋘ 𝑞
[21]. Цей алгоритм складається з двох кроків:
 власне квантовий алгоритм, який приймає на вхід генератор групи g і елемент 𝑥 = [𝑑]𝑔 і повертає, як результат пару (𝑘, 𝑗) і [𝑒]𝑔, що ігнорується;
 класичний алгоритм, що приймає на вхід пару (𝑘, 𝑗) і повертає, як результат шуканий дискретний логарифм 𝑑, якщо пара «хороша», тобто відповідає певним вимогам.
Цей алгоритм потребує 2[log
2
𝑞] регістрів для індексу і обчислення двох квантових перетворень Фур’є розміру 2
[log
2
𝑞]
. Теоретична нижня границя вірогідності отримання шуканого дискретного логарифму з першого запуску дорівнює 2
−10
Зокрема, ми розглянемо особливий випадок, де 𝑞 ≥ 2 2ℓ
− (2
ℓ
− 1)𝑑 і де d - на
інтервалі 0 < 𝑑 < 2
ℓ
для якогось цілого числа ℓ.
 нехай |Ψ⟩ =
1
√2 3ℓ
∑
∑
|a⟩|b⟩|0⟩
2
ℓ
−1
𝑏=0 2
2ℓ
−1
𝑎=0
де перший і другий регістри мають довжину мають довжину ℓ та 2ℓ відповідно;
 розрахуємо [𝑎]𝑔 ⊙ [−𝑏]𝑥 і збережемо результат у третій регістр і отримаємо формулу (3.10).
|Ψ⟩ =
1
√2 3ℓ
∑ ∑ |a, 𝑏, [𝑎]𝑔 ⊙ [−𝑏]𝑥 ⟩
2
ℓ
−1
𝑏=0 2
2ℓ
−1
𝑎=0
=
=
1
√2 3ℓ
∑
∑
|a, 𝑏, [𝑎 − 𝑏𝑑]𝑔 ⟩
2
ℓ
−1
𝑏=0 2
2ℓ
−1
𝑎=0
(3.10)

50
 розрахуємо QFT розміру 2 2ℓ
на першому регістрі і QFT розміру
2
ℓ
на другому регістрі і одержимо стан вираженний формулою (3.11);
|Ψ⟩ =
1
√2 3ℓ
∑
∑
|a, 𝑏, [𝑎 − 𝑏𝑑]𝑔 ⟩
2
ℓ
−1
𝑏=0 2
2ℓ
−1
𝑎=0
𝑄𝐹𝑇
→
𝑄𝐹𝑇
→
1
√2 6ℓ
∑
∑
∑
∑
𝑒
2𝜋𝑖(𝑎𝑗+2
ℓ
𝑏𝑘) 2 2ℓ
⁄
|j, 𝑘, [𝑎 − 𝑏𝑑]𝑔 ⟩
2
ℓ
−1
𝑘=0 2
2ℓ
−1
𝑗=0 2
ℓ
−1
𝑏=0 2
2ℓ
−1
𝑎=0
(3.11)
 проведемо вимірювання для того щоб отримати пару (j, 𝑘) і [𝑒]𝑔.
Пара (j, 𝑘) використовується далі в послідовному алгоритмі для знаходження дискретного логарифму.
Таким чином, за допомогою вищенаведеної модифікаціїї алгоритму Шора можна дость швидко знайти дискретний логарифм для у випадку використання особливих груп для яких виконується наступна тотожність 𝑞 ≥ 2 2ℓ
− (2
ℓ
− 1)𝑑.
Окрім описаних модифікації існують і інші модифікаіїї алгоритму Шора для певних абелієвиї груп та еліптичних кривих, але їх опис виходить за рамки даної роботи.

51
4 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМІВ ДЛЯ ОБЧИСЛЕННЯ
ДИСКРЕТНОГО ЛОГАРИФМУ
4.1 Реалізація не квантових алгоритмів пошуку дискретного логарифму
Для реалізації класичних алгоритмів для пошуку дискретного логарифму було обрано мову програмування Java. Вибір мови було обумовлено попереднім досвідом використання і тим що Java зарекомендувала себе, як мова програмування що підходить для розробки, як невеликих алгоритмів, так і величезних програмних систем. Для тестування продуктивності було обрано інструмент JMH [22], який немає гідних альтернатив в Java екосистемі і забезпечує правильні умови для вимірювання продуктивності коду, як то:
 виконання циклів розігріву перед початком основного тестування, завдяки яким JIT-компілятор встигає приступити до роботи і тим самим забезпечується реалістичність тестування;
 створення окремого інстансу JVM для забезпечення ізоляції коду під час тестування;
 врахування статистичної похибки у отриманих результатах та багато
іншого.
В наступних розділах описані реалізовані класичні алгоритми для пошуку дискретного логарифму.
4.1.1 Алгоритм Гельфонда – Шенкса
На вхід алгоритму подаються: G – циклічна група порядку n, генератор
α і деякий елемент β

52
Алгоритм складається з наступних кроків: а) Знаходимо m ← √𝑛 + 1 б) Обчислюємо γ ← 𝛼
𝑚
в) Для будь якого 𝑖 де 0 < 𝑖 < 𝑚:
1) Записати в таблицю (
𝑖, 𝛾).
2) Вирахувати
γ ← γ ∙ 𝛼
𝑚
г) Для будь-якого j.де 0 ≤ j ≤ m:
1) Вирахувати
α
2) Перевірити, чи знаходиться
β𝛼
𝑗
в таблиці
3) Повернути
𝑖𝑚 − 𝑗 якщо так, або продовжити виконання циклу.
Теоретична складність цього алгоритму в найгіршому випадку дорівнює O(√𝑛).
4.1.2 ρo-алгоритм Полларда для дискретного логарифма
Цей алгоритм виконує випадковий пошук дискретних логарифмів, як і алгоритм
Гельфонда - Шенкса, але він потребує меншого об’єму пам’яті для збереження даних, тому кращій для практичних цілей.
В основі даного алгоритму лежить та ж ідея, що й в основі ро-алгоритму для факторизації – спочатку будується псевдовипадкова послідовність, в якій знаходяться співпадаючи елементи за допомогою алгоритму Флойда, а потім на базі отриманої величини вираховується шуканий дискретний логарифм.
Нехай треба розрахувати log
𝑔
𝑎в кінцевій групі 𝐺 порядку 𝑛
Група 𝐺 розбивається на три непересічних підмножини приблизно рівної потужності: 𝐺 = 𝑆
1
𝑈𝑆
2
𝑈𝑆
3
, так щоб
1 ∉ 𝑆
2
. Причому розбиття повинно бути побудоване таким чином, щоб перевірка, до якої підмножини належить даний елемент
𝑥, була простою.

53
Наприклад, якщо 𝐺 = 𝑍
𝑝
, де
𝑝 – просте число, то можна задати розбиття 𝑆
1
=
{1, … , [
𝑝
3
]} , 𝑆
2
= {[
𝑝
3
] , … , [
2𝑝
3
]} , 𝑆
3
= {[
2𝑝
3
] , … , 𝑝 − 1}, або розбиття може бути таким: якщо 𝑥 𝑚𝑜𝑑 3 = 1, то 𝑥 ∈ 𝑆
1
, якщо
𝑥 𝑚𝑜𝑑 3 = 2, то 𝑥 ∈ 𝑆
2
, якщо
𝑥 𝑚𝑜𝑑 3 = 0, то 𝑥 ∈
𝑆
3
Далі на 𝐺 задається послідовність 𝑥
0
, 𝑥
1
, 𝑥
2
, … , де 𝑥
0
= 1, а 𝑥
𝑖+1
вираховується по 𝑥
𝑖
за допомогою функції
𝑓для 𝑖 ≥ 0:
𝑥
𝑖+1
= 𝑓(𝑥
𝑖
) = {
𝑎𝑥
𝑖
,
якщо 𝑥
𝑖
∈ 𝑆
1
𝑥
𝑖
2
,
якщо 𝑥
𝑖
∈ 𝑆
2
𝑔𝑥
𝑖
,
якщо 𝑥
𝑖
∈ 𝑆
3
Обчислення проводяться у групі 𝐺, тобто якщо 𝐺 = 𝑍
𝑚
, то розрахунки треба робити по модулю m.
Така послідовність групових елементів може бути представлена двома послідовностями: {𝑢
0
, 𝑢
1
, 𝑢
2
, … } та {𝑣
0
, 𝑣
1
, 𝑣
2
, …} такими, що 𝑥
𝑖
= 𝑔
𝑢
𝑖
𝑎
𝑣
𝑖
,1 при
𝑢
0
=
𝑣
0
= 0, і
𝑢
𝑖+1
= {
𝑢
𝑖
,
якщо 𝑥
𝑖
∈ 𝑆
1 2𝑢
𝑖
,
якщо 𝑥
𝑖
∈ 𝑆
2
𝑢
𝑖
+ 1,
якщо 𝑥
𝑖
∈ 𝑆
3
𝑣
𝑖+1
= {
𝑣
𝑖
+ 1, якщо 𝑥
𝑖
∈ 𝑆
1 2𝑣
𝑖
, якщо 𝑥
𝑖
∈ 𝑆
2
𝑣
𝑖
, якщо 𝑥
𝑖
∈ 𝑆
3
Обчислення в послідовностях 𝑢 и 𝑣 виконуються по модулю 𝑛.
В силу того, що група 𝐺 – кінцева, за допомогою алгоритму Флойда можна знайти такі 𝑥
𝑖
и 𝑥
2𝑖
, что 𝑥
𝑖
= 𝑥
2𝑖
. Тогда 𝑔
𝑢
𝑖
𝑎
𝑣
𝑖
= 𝑔
𝑢
2𝑖
𝑎
𝑣
2𝑖
⇒ 𝑎
(𝑣
2𝑖
−𝑣
𝑖
)
= 𝑔
(𝑢
2𝑖
−𝑢
𝑖
)
Логарифмувавши за основою 𝑔 обидві частини даного рівняння, отримуємо:

54
(𝑣
𝑖
− 𝑣
2𝑖
) log
𝑔
𝑎 ≡ (𝑢
2𝑖
− 𝑢
𝑖
)(𝑚𝑜𝑑 𝑛)
Вирішивши це порівняння, отримуємо шуканий логарифм. (Варто зауважити, що якщо 𝐺 = 𝑍
𝑚
∗
, то 𝑛 = 𝜑(𝑚).
Асимптотична складність даного метода дорівнює O(√𝑛), где 𝑛 – порядок групи
𝐺.
4.1.3 Алгоритм Поліґа-Геллмана
На вхід алгоритму подаються генератор 𝛼 циклічної групи G порядку n і елемент
β циклічної групи.
Алгоритм складається з наступних кроків: а) Знайти розкладення на прості множники для n 𝑛 = 𝑝
1
𝑒
1
𝑝
2
𝑒
2
… 𝑝
𝑟
𝑒
𝑟
, де
𝑒
𝑖
≥ 1 б) Для 𝑖 від 1 до 𝑟 робимо наступне: (Обчислити 𝑥
𝑖
= 𝑙
0
+ 𝑙
1
𝑝
𝑖
+ ⋯ +
𝑙
𝑒
𝑖
−1
𝑝
𝑖
𝑒
𝑖
−1
де
𝑥
𝑖
= 𝑥 𝑚𝑜𝑑 𝑝
𝑖
𝑒
𝑖
):
1) Покласти
γ ← 1 і 𝑙
−1
← 1 2) Обчислити
α ← αn 𝑝
𝑖
⁄
3) Обчислити
𝑙
𝑗
. Для j від 0 до e i
− 1 робимо наступне:
 Обчислити γ ← γ𝛼
𝑙
𝑗−1
𝑝
𝑖
𝑗−1
і
β̅ ← (βγ
−1
)
n 𝑝
𝑖
𝑗+1
⁄
 Обчислити 𝑙
𝑗
← log
α
β
4) Встановити
𝑥
𝑖
← 𝑙
0
+ 𝑙
1
𝑝
𝑖
+ ⋯ + 𝑙
𝑒
𝑖
−1
𝑝
𝑖
𝑒
𝑖
−1
в) Використати, наприклад, алгоритм Гаусса для обчислення цілого x, 0 ≤ x ≤
n − 1.такий що x ≡ 𝑥
𝑖
(𝑚𝑜𝑑 𝑝
𝑖
𝑒
𝑖
) для 1 ≤ i ≤ r г) Повернути (x)

55
Асимптотична складність цього алгоритму в найгіршому випадку дорівнює
O(√𝑛)), де 𝑛 – порядок групи 𝐺.
4.1.4 Структура програмного коду
Вищеописані алгоритми були реалізовані з використанням мови програмування
Java. Алгоритм прямого перебору було розпаралелено, так як в однопоточному варіанті його продуктивність є дуже низькою і не варта розгляду.
Алгоритми були реалізовані керуючись принципами і найкращими практиками
ООП. Окрім безпосередньо алгоритмів, були реалізовані класи які містять код для генерації випадкових простих чисел та генерації примітивних коренів, а також класи для рішення систем конгруенцій, які використовуються у алгоритмі Пухлінга-
Хелмана.
Розглянемо діаграму класів зображену на рисунку 4.1.
Рисунок 4.1 – Діаграма класів реалізації класичних алгоритмів для пошуку дискретного логарифму

56
З рисунку видно, що основна реалізована логіка була схована за двома
інтерфейсами, а саме інтерфейсом DiscreteLogProblemSover, який реалізують усі алгоритми пошуку дискретного логарифму (окрім алгоритму Пухлінга-Хелмана, так як він має дещо відмінній інтерфейс і, у свою чергу, використовує алгоритм
Полдарда), і CongruenceSystemSolver, реалізація якого направлена на вирішення системи конгруенцій. Окрім класів, які містять код безпосередньо алгоритмів, було додано кілька службових класів які інкапсулюють деякі примітивні операції над простими числами, а також алгоритми генерації простих чисел та примітивних коренів, які використовуються, як в алгоритмах, так і для генерації даних для тестування.
Ці класи – це DefinetePrime (містить операції над простими числами),
SafePrimeGen (використовується для генерації простих чисел) і PrimRootGen
(використовується для генерації примітивних коренів).
4.1.5 Результати тестування продуктивності алгоритмів за допомогою JMH
JMH дозволяє досить точно вимірювати продуктивність функцій за декількома критеріями, такими, як пропускна здатність, середній час виконання, обраний час виконання (коли один результат з великої кількості запусків обирається за еталон) і т.і. Завдяки цим якостям інструмент JMH де-факто визнаний чи не єдиним
інструментм для більш-менш точного виміру продуктивності Java-додатків, який дозволяє розробляти досить гнучкі і правильні, з точки зору теорії вимірювання продуктивності, тести.
На рисунку 4.2 наведено результати тесту продуктивності для реалізованих класичних алгоритмів пошуку дискретного логарифму.

57
Рисунок 4.2 – Результати тестування продуктивності не квантових алгоритмів пошуку дискретного логарифма
Для кожного за алгоритмів наведено середній час виконання і окремо, випадково взятий зразковий час (sample time). Тобто результати можна вважати досить показовими. Результати тестів приведені згори вниз для: алгоритму простого перебору, алгоритму Гельфонда-Шенкса, алгоритму Пухлінга-Хелмана і алгоритму
Полларда-Ро.
Власне порівняння швидкодії алгоритмів зображене на рисунку 4.3. З рисунку видно результати вимірювання продуктивності, з яких виходить, що найповільнішим алгоритмом є BruteForce, тобто простий перебір варіантів (в нашому випадку він був розпаралелений на 8 потоків, для 1 потоку результати ще гірші). Він у середньому виконувався за 28 мілісекунд, наступний за продуктивністю алгоритм Гельфонда –
Шенкса, або BabyStepGiantStep, він, у середньому, виконувався за 5 мілісекунд. 1 та 2 місце ділять алгоритм Поліґа-Геллмана та ρo-алгоритм Полларда, з 0,9 та 1,4 мілісекундами відповідно.

58
Рисунок 4.3 – Результати тестування продуктивності не квантових алгоритмів пошуку дискретного логарифма
Тести виконувалися на наступному обладнанні з ОС Windows: Intel Core i7-
6700k 4.5GHz, DDR4 32Gb ОЗП.
4.2 Реалізація квантового алгоритму Шора пошуку дискретного логарифму
У цьому розділі наведено відомості про обрання відповідного інструментарію для розробки алгоритму Шора. Опис інструментарію та різних його характеристик, таких як якість документаціїї, накільки інструментарій інтегрований в інтегровані середовища розробки, та наскільки багаті стандартні бібліотеки представлені у розгладаному інструментарії. Деталі реалізації та результати тестування квантового алгоритму.
28 5
1,4 0,9
B R U T E F O R C E
B S G S
P O L L A R D - R H O
P O H L I N G - H E L L M A N
Time (in ms)

59 4.2.1 Вибір інструментів для реалізації
На сьогоднішній день існують десятки, як бібліотек, так і окремих інструментів
(або мов) для написання квантових програм і їх запуску на емуляторі квантового комп’ютера [23]. При виборі інструменту для реалізації квантового алгоритму Шора для пошуку дискретного логарифма було визначено ряд критеріїв, яким повинен відповідати обраний інструмент. На основі цих критеріїв було вибрано і порівняно декілька підходящих інструментів. Інструменти повинні відповідати наступним критеріям:
 підтримка написання коду статично типізованою мовою програмування;
 наявність ефективного квантового емулятора;
 багата стандартна бібліотека, яка полегшувала та пришвидшувала процес розробки;
 зручна інтеграція в інтегровані середовища розробки;
 наявність добре сформованих навчальних матеріалів та документації.
Серед наявних інструментів було обрано три, які повністю відповідають вищенаведеним критеріям:
 QCGPU;
 QuEST;
 Microsoft QDK.
Для порівняння цих інструментів скористуємося методом варіантних мереж.
Оцінимо за п'ятибальною шкалою наступні характеристики програмних продуктів: а) швидкість і простота розробки (5). б) підтримка інструменту в інтегрованих середовищах розробки (3). в) багатство стандартної бібліотеки (5). г) якість документації (4). д) легкість інсталяції розробленого програмного забезпечення (3).

60 е) підтримка мультиплатформеності (2).
В круглих дужках вказана важливість кожної з характеристик.
Для рішення завдання вибору найкращого інструменту для розробки скористуємося методом варіантних мереж. Результат розрахунку придатності того чи
іншого інструменту наведено у таблиці 4.1.
Таблиця 4.1 – Рішення завдання вибору програмного забезпечення
Середовище розробки
Характеристика
Сума а (5) б (3) в (5) г (4) д (3) е (2)
QCGPU
4 3
3 3
4 4
76
QuEST
5 3
3 3
4 4
75
Microsoft QDK
5 5
5 5
4 4
105
Як видно з таблиці, найкращім інструментом за сукупністю результатів по усіх характеристик виявися набір для розробки квантових програм від компанії Microsoft
– QDK.
QDK включає в себе емулятор квантового комп’ютера який можна запускати в
CLI середовищі, мову програмування Q# та багату стандартну бібліотеку.
Мова програмування Q# була нещодавно розроблена компанією Microsoft з метою розповсюдження знань про квантові алгоритми та надання можливості реалізації квантових алгоритмів за допомогою оптимізованих квантових примітивів, які входять в стандартну бібліотеку мови Q#. На зображено структуру QDK.
Q# підтримує парадигму квантового програмування і може бути легко
інтегрована з іншими технологіями та мовами Microsoft (C#, F#, ASP.NET і т.д.).
Стандартна бібліотека QDK включає усі необхідні для реалізації функції та примітиви. Так, наприклад, простір імен Microsoft.Quantum.Convert, як можна здогадатися з назви, включає в себе набір функцій для конвертації між різними типами

61
Q#. Простір імен Microsoft.Quantum.Intrinsic складається з методів що відтворюють роботу базових гейтів, а Microsoft.Quantum. Сanon містить методи для перетворення гейтів (наприклад метод CControlled, що перетворює звичайну операцію на контрольовану). Структуру стандартної бібліотеки QDK можна побачити на рисунку
4.4
Рисунок 4.4 – Структура QDK
QDK має інтеграцію з такими середовищами розробки, як Visual Studio, Visual
Studio Code і навіть IntelliJ IDEA.
4.2.2 Реалізація алгоритму і її результати
Для практичної реалізації за основу було взято алгоритм описаний Нільсеном
М.А. та Чуангом І.Л [24]
Структуру проекту реалізації квантового алгоритму Шора можна побачити на рисунку 4.5
Реалізація алгоритму складається з частини коду написаній на C#
(ShorRunner.cs) та частини коду написаній на Q# (DiscreteLogShor.qs).
ShorRunner.cs містить у собі код для взаємодії з користувачем (зчитування користувацького вводу) та для запуску квантового алгоритму на симуляторі.

62
Рисунок 4.5 – Структура проекту
DiscreteLogShor.qs містить власне квантовий алгоритм Шора пошуку дискретного логарифму, розбитий на декілька функцій. Далі наведено код основної функції алгоритму:
// Discrete logarithm Algorithm
// Input: integers a, b, N
// Goal: compute the discrete logarithm log_a(b), returns -1 on failure cases operation DiscreteLogShor (a: Int, b: Int, N: Int) : Int { mutable appr_slmodr = 0; mutable appr_l = 0; let order = N - 1; // Euler function
Message($"Order is ={order}"); let t = BitSizeI(N) * 2 + 1;
Message($"Register size is ={t}"); using ((x1, x2, y) = (Qubit[t], Qubit[t], Qubit[t])) {
ApplyToEach(H, x1);
ApplyToEach(H, x2);
DLOracle(a, b, N, x1, x2, y);
InverseQFT(x1);
InverseQFT(x2); set appr_slmodr =
MeasureInteger(BigEndianAsLittleEndian(BigEndian(x1))); set appr_l = MeasureInteger(BigEndianAsLittleEndian(BigEndian(x2)));
ResetAll(x1);
ResetAll(x2);
ResetAll(y);
} let (slmodr, _) = (ContinuedFractionConvergentI(Fraction(appr_slmodr, t),
N))!;

63 let (l, _) = (ContinuedFractionConvergentI(Fraction(appr_l, t), N))!; if (GreatestCommonDivisorI(l, order) != 1) {
Message($"Algorithm failed due to measure l={l}, no coprime to r={order}"); return -1;
} let l_inv = InverseModI(l, order); let s = slmodr * l_inv % order; return s;
}
На вхід алгоритму подається 3 числа: основа логарифму (генератор циклічної групи), число що треба логарифмувати і модуль циклічної групи (N). Далі виділяються
3 квантові регістри розміру: кількість бітів
𝐵𝑖𝑡𝑆𝑖𝑧𝑒(𝑁) ∗ 2 + 1. Далі до перших двох регістрів застосовується гейт Адамара.
Після цього виконується DiscreteLogOracle(DLOracle), в рамках якого проходять основні математичні дії над квантовими регістрами, а саме зведення у ступінь по модулю кожного з вірогідних значень регістрів за формулою (4.1)
1
𝑞
∑ ∑ |𝑥, 𝑦 >
𝑞−1
𝑦=0
𝑞−1
𝑥=0
→
1
𝑞
∑ ∑ |𝑥, 𝑦, 𝛼
𝑥
𝛽
𝑦
>
𝑞−1
𝑦=0
𝑞−1
𝑥=0
(4.1)
У коді ця операція виглядає наступним чином:
// Oracle U|x1⟩|x2⟩|y⟩ → |x1⟩|x2⟩|y ⊕ f(x1,x2)⟩ where f(x1,x2)=b^x1*a^x2 mod N
// Input: integers a, b, and N, registers x1, x2, and qs. operation OracleFunc (a : Int, b : Int, N : Int, x1 : Qubit[], x2 : Qubit[], qs : Qubit[]) : Unit { body(...) {
X(qs[Length(qs) - 1]);
PowerOfa(b, N, x1, qs);
PowerOfa(a, N, x2, qs);
} adjoint auto; controlled auto; adjoint controlled auto;
}
PowerOfa у даному випадку відповідає за операцію, яка описана формулою (4.2).

64
|x⟩|y⟩ → |x⟩|a x
∗ y mod N⟩
(4.2)
Після завершення роботи оракула, над першим та другим регістром виконується
інвертоване перетворення Фур’є і з регістрів дістаються числові значення. Далі виконується пошук збіжного безперервного дробу (ContinuedFractionConvergent) по
N, як знаменнику на основі, виміряних з квантових регістрів, приблизних значень.
В результаті зберігаємо необхідні значення числівників знайдених дробів, як slmodr та l. Далі l та N – 1 на взаємну простоту. Якщо вони не взаємно просто, цей запуск алгоритму провалено і треба робити новий запуск. Якщо ж умова взаємної простоти виконана, то знаходимо логарифм, як slmodr помножений на (зворотній модуль l по N -1 по модулю N -1).
Реалізований алгоритм завершив роботу тільки для найпростішої циклічної групи за модулем 3. При цьому час його виконання наблизився дорівнював 2 годинам
57 хвилинам. Таке довгострокове виконання пояснюється використанням емулятора замість реального квантового комп’ютера, так, як емулювання квантових ефектів потребує значного часу і оперативної пам’яті. Навіть для циклічної групи за модулем
5, споживання оперативної пам’яті виходило за межі 100 гігабайт (так як треба було емулювати роботу 28 кубітів не враховуючи проміжні кубіти, що використовувалися у бібліотечних методах) , після чого робота програми завершувалася з помилкою в емуляторі.
Наразі можна впевнено констатувати, що в найближче десятиріччя квантові комп’ютери загалом і зокрема алгоритм Шора неможливо буде використати для злому криптографічних систем, робота яких базується на використанні складності знаходження дискретного логарифму. Цей висновок випливає з факту, що навіть у теорії алгоритм Шора пошуку дискретного логарифму потребує 6n кубітів. Де n – число байт в модулі циклічної групи.
Враховуючи що сучасний рекомендований розмір модуля для протоколу Діффі-
Хеллмана дорівнює 2048 бітам [25], для його злому буде потрібен 12288-кубітний

65 квантовий комп’ютер. В той час, як найбільший сучасний квантовий комп’ютера складається з 72 кубіт (не враховуючи квантові комп’ютери від D-Wave Systems, які не являються такими для повного спектра задач) [26]. Тобто квантові комп’ютери все ще на здатні конкурувати зі звичайними та суперкомп’ютерами у вирішенні NP-задач.
Тим не менш, працездатність алгоритма Шора практично доведена і область досідження і розробки квантових комп’ютерів розвивається досить швидко.
Зважаючи на це, вже варто починати впровадження пост-квантових криптографічних алгоритмів на підприємствах, і, що більш важливо, необхідно почати перехід до пост- квантової криптографії для клієнтів та серверів, чия комунікація відбувається через відкриті інтернет канали. Варто також зауважити, що деякі хеш-функції таком можуть бути зламані за допомогою квантових комп’ютерів, тому перехешування паролів користувачів – це також важливий корок у пост-квантову еру.

66

1   2   3   4

скачати