ПОРІВНЯННЯ АЛГОРИТМІВ ФАКТОРИЗАЦІЇ ДЛЯ КВАНТОВОГО ТА КЛАСИЧНОГО КОМП’ЮТЕРІВ - Scientific conference
Main page
UA RU EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

ПОРІВНЯННЯ АЛГОРИТМІВ ФАКТОРИЗАЦІЇ ДЛЯ КВАНТОВОГО ТА КЛАСИЧНОГО КОМП’ЮТЕРІВ

23.09.2022 13:55

[1. Information systems and technologies]

Author: Лучинська Тетяна Степанівна, студентка 2 курсу магістратури, кафедра програмування, Львівський національний університет ім. Івана Франка


Метою даного дослідження є порівняння класичних та квантових алгоритмів для вирішення задачі факторизації цілих чисел, систематизація матеріалів та наукових досліджень про вже існуючі алгоритми, а також розробка програмного забезпечення, що дозволить користувачам обирати метод для розкладання заданого числа на прості множники.

Актуальність: сьогодні, в час війни, вкрай необхідно розвивати науково-технічний потенціал України, зокрема в напрямках, що можуть бути корисними в кібербезпеці. Одним з них є розв’язання задачі факторизації за поліноміальний час. Такий алгоритм представив Пітер Шор у 1994 році. З того часу ведеться безліч дискусій про надійність алгоритму шифрування RSA.

Практичне значення: розроблене програмне забезпечення може бути використане в навчальних цілях на лекціях з основ програмування, квантових обчислень, алгоритмів і структур даних. Створений програмний застосунок, звісно, не зможе розшифрувати алгоритм RSA, проте дозволить вирішити проблему факторизації для невеликих чисел на квантовому 4 емуляторі та класичному комп’ютері.

Проблема факторизації

Факторизація натурального числа, тобто задача пошуку всіх його простих дільників належить до найважливіших задач криптології. На сьогоднішній день задача є актуальною. Найефективніший з відомих алгоритмів потребує часу 





причому в найкращому випадку c=1 [2].


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


Огляд алгоритму Шора


Перша реалізація алгоритму Шора з часу його публікації була проведена вже через 7 років (у 2001р.) для числа 15 групою спеціалістів IBM в Стенфордському університеті. Число 15 тоді було розкладено на множники 3 і 5 за допомогою квантового комп’ютера з сімома кубітами.


Алгоритм складається з двох частин. Перша частина алгоритму перетворює задачу розкладання в задачу знаходження періоду функції і може бути реалізована класично. Друга частина знаходить період за допомогою квантового перетворення Фур’є і відповідає за квантове прискорення.


Алгоритм визначення періоду Шора в значній мірі покладається на здатність квантового комп’ютера перебувати в багатьох станах одночасно, тобто суперпозицію. Щоб обчислити період функції f, ми оцінюємо функцію в усіх точках одночасно.


В алгоритм Шора було внесено багато модифікацій. Наприклад, якщо у випадку оригінального алгоритму Шора та з деякими іншими модифікаціями на квантовому комп’ютері необхідно виконати від двадцяти до тридцяти запусків, то у випадку модифікації, зробленої Девідом МакЕналлі з Університету Квінсленда, на квантовому комп’ютері потрібно лише чотири-вісім запусків.


Огляд алгоритмів для класичного комп’ютера


Найпростіший очевидний спосіб факторизації - це створення списку простих чисел і перевірка числа на ділення без залишку для кожного з цих чисел. Однак цей процес займе багато часу, якщо просто створити багато циклів, тому потрібно використовувати математичний алгоритм.


Є відомим алгоритм решета Ератосфена, це простий спосіб генерувати велику кількість простих чисел, однак для ефективного використання його також необхідно оптимізувати. 


Підхід з використанням решета Ератосфена такий: після створення списку простих чисел перевіряється кожне число з числом яке факторизується. 


Ро-алгоритм Полларда відомий тим, що при повній оптимізації потребує менше однієї секунди для знаходження простих множників для числа, що складається зі 100 цифр. У  всіх  ρ-методах  Полларда  будується послідовність, елементи  якої утворюють  цикл, починаючи  з  деякого номера n, що може бути проілюстровано розташуванням чисел у вигляді грецької букви ρ. Це і послужило назвою для сімейства методів. Складність даного алгоритму оцінюється як O(N1/4). 


Результати програмної реалізації


Веб-застосунок для факторизації чисел було розроблено із застосуванням клієнт-серверної архітектури. Для реалізації серверної частини було використано мову програмування Python. Для розробки квантового алгоритму Шора було використано QisKit. Це фреймворк з відкритим кодом для роботи із квантовим комп'ютером. Має хорошу документацію і дозволяє працювати з реальним квантовим комп'ютером від ІВМ. 


Для розробки веб-застосунку використано відкриту JavaScript бібліотеку React. Ця бібліотека дозволяє не перезавантажувати сторінку для оновлення даних. Для побудови графіків використано бібліотеку recharts.


Після розробки програмного забезпечення було проведено тестування для перевірки результатів. Для полегшення аналізу програма одразу будує графік з отриманими результатами.


Спочатку було перевірено роботу класичних алгоритмів. На рис. 1 можна побачити графік з часом роботи алгоритму по осі Y, та номером досліду по осі X. Спочатку проведено тестування числа 15 - обидва алгоритми знайшли множники за 0 с. Для більшого числа 7301579 час роботи решета Ератосфена значно зріс (2.7 с.), а результати Ро-алгоритму Полларда майже не змінилися (все ще близькі до 0 і збігаються з віссю Y).







Рис. 1. Результат виконання класичних алгоритмів


На рисунку 2 зображено тестування квантових алгоритмів. Було реалізовано власний алгоритм Шора для факторизації числа 15 (Шор 15 на графіку), а також використано алгоритм Шора з бібліотеки QisKit (Шор на графіку), який дозволяє факторизувати також число 21. На жаль, для більших чисел вже з'являлися помилки про недостатню кількість пам'яті. 







Рис. 2. Результат виконання квантових алгоритмів


Висновки


Було реалізовано квантовий алгоритм Шора для числа 15, та проведено порівняння часу його роботи з алгоритмом Шора з бібліотеки QisKit та класичними алгоритмами з використанням решета Ератосфена та Ро-алгоритмом Полларда. На жаль, час отримання результатів на квантовому емуляторі значно перевершив час роботи класичних алгоритмів. Також квантові емулятори не дозволяли працювати з числами більше 21. 


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


Література


1. Карлаш Г. Ю. Квантові інформаційні системи. Навчальний посібник для спеціальності «Прикладна фізика та наноматеріали». Київ: факультет радіофізики, електроніки та комп’ютерних систем Київського національного університету імені Тараса Шевченка, 2018. – 77 с.


2. Стасюк М. Ф. Деякі підходи до проблем факторизації. Збірник наукових праць п’ятої Міжнародної науково-практичної конференції «Інформаційно-комунікаційні технології в сучасній освіті: досвід, проблеми, перспективи». Львів. 2017. С. 84-88.


____________________


Науковий керівник: Рикалюк Роман Євстахович, доцент кафедри програмування, Львівський національний університет ім. Івана Франка





Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення