Browsing by Author "Грищук, О. В."
Now showing 1 - 1 of 1
- Results Per Page
- Sort Options
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 в універсальних комп'ютерних системах. Реалізації математичними та криптографічними програмними бібліотеками функції обчислення модульної експоненти використовує більш оптимальний алгоритм множення за модулем, так зване множення Монтгомері. У розроблених трьох функціях використовуються операції множення за модулем для множників менших за значення модуля. Окремо проаналізовано функцію з використанням передобчислення залишків для фіксованої основи та модуля, що може ефективно використовуватись для обчислення дискретного логарифму.