The modular exponentiation with precomputation of redused set of residues for fixed-base

Abstract

EN: Context. Modular exponentiation is an important operation in many applications that requires a large number of calculations 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 program that uses the precomputation of redused set of residuals for fixed-base. Method. Modular exponentiation is implemented using of the development of the right-to-left binary exponentiation method for a fixed basis with precomputation of redused set of residuals. To efficient compute the modular exponentiation over big numbers, the property of a periodicity for the sequence of residuals of a fixed base with exponents equal to an integer power of two is used. Results. Comparison of the runtimes of five variants of functions for computing the modular exponentiation is performed. In the algorithm with precomputation of redused set of residuals for fixed-base provide faster computation of modular exponentiation for values larger than 1K binary digits compared to the functions of modular exponentiation of the MPIR and Crypto++ libraries. 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. 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 the precomputation of redused set of residuals for fixed-base. The software implementation of modular exponentiation with increasing from 1K the number of binary digit of exponent shows an improvement of computation time with comparison with the functions of modular exponentiation of the MPIR and Crypto++ libraries. UK: Актуальність. Модульне піднесення до степеня є важливою операцією в багатьох застосуваннях, що вимагає великої кількості обчислень. Швидкі обчислення модульної експоненти вкрай необхідні для ефективних обчислень у теоретично-числових перетвореннях, для забезпечення високої криптостійкості інформаційних даних та в багатьох інших завданнях. Мета – аналіз часу виконання програмних функцій розрахунку модульної експоненти з розробленою програмою, що використовує попереднє обчислення зменшеного набору залишків для фіксованої бази. Метод. Модульне піднесення до степеня реалізовано з використанням методу двійкового зсуву справа наліво для фіксованого базису з попереднім обчисленням зменшеного набору залишків. Для ефективного обчислення модульної експоненти великих чисел використовується властивість періодичності послідовності залишків фіксованої бази з експонентами, що дорівнюють цілочисельній степені двійки. Результати. Проведено порівняння часу виконання п’яти варіантів функцій для обчислення модульного піднесення до степеня. В алгоритмі з попереднім обчисленням зменшеного набору залишків для фіксованої бази забезпечується більш швидке обчислення модульної експоненти для значень даних, що перевищують 1K двійкових розрядів, порівняно з функціями модульного піднесення до степеня бібліотек MPIR і Crypto++. Бібліотека MPIR з цілочисельним типом даних з кількістю двійкових розрядів від 256 до 2048 біт використовується для розробки алгоритму обчислення модульного піднесення до степеня. Висновки. У роботі розглянуто та проаналізовано розроблену програмну реалізація обчислення модульної експоненти на універсальних комп’ютерних системах. Одним із способів реалізації прискорення обчислення модульного піднесення до степеня є розробка алгоритмів, які можуть використовувати попереднє обчислення зменшеного набору залишків для фіксованої бази. Програмна реалізація модульного піднесення до степеня зі збільшенням від числа 1K двійкових розрядів даних показує покращення часу обчислень у порівнянні з функцією модульного піднесення до степеня бібліотек MPIR та Crypto++.