The runtime analysis of computation of modular exponentiation

Abstract

EN: Context. Providing the problem of fast calculation of the modular exponentiation requires the development of effective algorithmic methods using the latest information technologies. Fast computations of the modular exponentiation are extremely necessary for efficient computations in theoretical-numerical transforms, for provide high crypto capability of information data and in many other applications. Objective – the runtime analysis of software functions for computation of modular exponentiation of the developed programs based on parallel organization of computation with using multithreading. Method. Modular exponentiation is implemented using a 2k-ary sliding window algorithm, where k is chosen according to the size of the exponent. Parallelization of computation consists in using the calculation of the remainders of numbers raised to the power of 2i modulo, and their further parallel multiplications modulo. Results. Comparison of the runtimes of three variants of functions for computing the modular exponentiation is performed. In the algorithm of parallel organization of computation with using multithreading provide faster computation of modular exponentiation for exponent values larger than 1K binary digits compared to the function of modular exponentiation of the MPIR library. The MPIR library with an integer data type with the number of binary digits from 256 to 2048 bits is used to develop an algorithm for computing the modular exponentiation with using multithreading. Conclusions. In the work has been considered and analysed the developed software implementation of the computation of modular exponentiation on universal computer systems. One of the ways to implement the speedup of computing modular exponentiation is developing algorithms that can use multithreading technology on multi-cores microprocessors. The multithreading software implementation of modular exponentiation with increasing from 1024 the number of binary digit of exponent shows an improvement of computation time with comparison with the function of modular exponentiation of the MPIR library. UK: Актуальність. Постановка проблеми швидкого обчислення модульної експоненти вимагає розробки ефективних алгоритмічних методів з використанням новітніх інформаційних технологій. Швидкі обчислення модульної експоненти є надзвичайно необхідними для ефективних обчислень у теоретико-числових перетвореннях, для забезпечення високої стійкості криптоінформаційних даних та у багатьох інших додатках. Мета – аналіз швидкості виконання функцій в програмному забезпеченні для обчислення модульної експоненти розроблених програм на основі паралельної організації обчислень з використанням багатопоточності. Метод. Обчислення модульної експоненти реалізується за допомогою алгоритму 2k-го ковзаючого вікна, де k вибирається відповідно до розміру показника степеня. Паралелізація обчислень полягає у використанні обчислення залишків чисел, піднесених до степеня 2i за модулем, та їх подальшого паралельного множення за модулем. Результати. Здійснено порівняння часу виконання трьох варіантів функцій для обчислення модульної експоненти. В алгоритмі паралельної організації обчислень з використанням багатопоточності забезпечується більш швидке обчислення обчислення модульної експоненти для значень показника степеня, що перевищує 1K двійкових цифр, порівняно з функцією обчислення модульної експоненти в бібліотеці MPIR. Бібліотека MPIR з цілочисельним типом даних з числом двійкових цифр від 256 до 2048 біт використовується для розробки алгоритму обчислення обчислення модульної експоненти з використанням багатопоточності. Висновки. У роботі розглянуто та проаналізовано розроблену програмну реалізацію обчислення модульної експоненти на універсальних комп'ютерних системах. Одним із способів реалізації прискорення обчислень обчислення модульної експоненти є розробка алгоритмів, які можуть використовувати багатопотокову технологію на багатоядерних мікропроцесорах. Багатопотокова програмна реалізація обчислення модульної експоненти зі збільшенням від 1024 числа двійкових розрядів показника степеня показує поліпшення часу обчислення у порівнянні з функцією обчислення модульної експоненти бібліотеки MPIR.