Ukrainian Journal of Information Technology. – 2022. – Vol. 4, No. 1

Permanent URI for this collectionhttps://ena.lpnu.ua/handle/ntb/61515

Науковий журнал

Видання "Український журнал інформаційних технологій" засновано у 2018 р. за рішенням вченої ради Інституту комп'ютерних наук та інформаційних технологій від 23 квітня 2018 р. Журнал є правонаступником збірника наукових праць "Вісник Національного університету "Львівська політехніка". Серія: Комп'ютерні науки та інформаційні технології", який входить до переліку фахових видань ВАК України, в яких можна друкувати матеріали дисертаційних робіт у галузі технічних наук.

Український журнал інформаційних технологій. – Львів : Видавництво Львівської політехніки, 2022. – Том 4, № 1. – 88 с. : il.

Український журнал інформаційних технологій

Зміст (том 4, № 1)


1
21
29
37
44
53
63
68
78
85

Content (Vol. 4, No 1)


1
21
29
37
44
53
63
68
78
85

Browse

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Порівняльний аналіз функцій обчислення модульної експоненти
    (Видавництво Львівської політехніки, 2022-02-28) Процько, І. О.; Рикмас, Р. В.; Грищук, О. В.; Protsko, I. O.; Rykmas, R. V.; Gryshchuk, O. V.; Національний університет “Львівська політехніка”; ТОВ "ЮніСервіс"; ТОВ "СофтСерв"; Lviv Polytechnic National University; LtdS "Uniservice"; LtdS "Softserve"
    Обчислення модульної експоненти для великих чисел широко використовується для знаходження дискретного логарифму, в теоретико-числових перетвореннях та в криптографічних алгоритмах. Для ефективного обчислення модульної експоненти проводяться дослідження нових методів, алгоритмів та засобів їх реалізації. Виділяють три напрями методів модульного піднесення до степеня: загальне модульне піднесення до степеня, та обчислення модульної експоненти з фіксованим показником або з фіксованою основою. Розроблено спеціальні функції для виконання піднесення до степені за модулем у математичних і криптографічних програмних бібліотеках. У роботі проведено порівняльний аналіз вільнодоступних функцій обчислення модульної експоненти з бібліотек Crypto++, OpenSSL, Pari/GP та MPIR та розроблених трьох функцій на основі алгоритму бінарного зсуву справа на ліво. Для роботи з великими числами у розроблених функціях використовується окремий тип числових даних з бібліотеки MPIR. Розроблені функції реалізують бінарний ітераційний алгоритм в одному основному потоці, у двох потоках та одному потоці з використанням передобчислення. За основу порівняння вибрано усереднений тривалість виконання обчислення модульної експоненти для псевдовипадкових даних розрядністю 1К і 2К біт, що відповідає розрядності біля 300 і 600 десяткових знаків. Результати часу виконання, що зведені у таблицю, показують, що найшвидше обчислюється модульна експонента функцією з бібліотеки OpenSSL в універсальних комп'ютерних системах. Реалізації математичними та криптографічними програмними бібліотеками функції обчислення модульної експоненти використовує більш оптимальний алгоритм множення за модулем, так зване множення Монтгомері. У розроблених трьох функціях використовуються операції множення за модулем для множників менших за значення модуля. Окремо проаналізовано функцію з використанням передобчислення залишків для фіксованої основи та модуля, що може ефективно використовуватись для обчислення дискретного логарифму.