The thesis is devoted to solving the urgent scientific and practical problem of increasing the efficiency of multi-digit numbers processing based on the use of vector-modular operations of modular multiplication and exponentiation, the perfect (PF) and the modified perfect forms (MPF) of the residue number system (RNS) to reduce time complexity, increase speed algorithms, specific software and hardware in asymmetric cryptosystems. The methods for searching the inverse element by modulo and performing the Chinese Remainder Theorem based on adding a module and adding a remainder were developed, which make it possible to parallelize the process of searching for the inverse element by modulo and, correspondingly, reduce the time complexity of this operation when it is used in asymmetric cryptosystems by using modular operation of adding the module or remainder. A method has been developed for searching for a multi-degree function by modulo, which avoids the operation of modular exposure of multi-digit numbers due to the double use of the Euler function, performing arithmetic operations on operands, less than a given module, and switching to linear congruence. Also, the method has been proposed for exploration of a set of RNS
modules, which, by calculating the coefficients of basic numbers based on analytical expressions when restoring a decimal number from a RNS, avoided the cumbersome operation of finding the multiplicative inverse element by modulo, respectively reducing the time complexity and increasing the speed of computing systems. Methods for constructing sets of PF RNS modules on the basis of fractional transformations and factorization were developed, which could reduce the time and hardware complexity when converting numbers from RNS to a decimal number
system by avoiding the search for a multiplicative inverse element by modulo and multiplying by it. Also, methods for constructing a three- and multi-module MPF RNS were discovered, which, through the use of analytical expressions obtained on the basis of fractional transformations, factorization, Viet's theorem, and solutions of congruence systems, could reduce the length of operands in intermediate calculations,
and avoided the operation of searching for the inverse element modulo and multiplying by it, reducing, respectively, the time complexity when restoring a decimal number from RNS. The expediency of using the MPF RNS in asymmetric cryptosystems instead of the existing integer form was substantiated. The Fermat’s method for multi-digit numbers factorization has been improved, which made it possible to reduce the lengths of operands, simplify the search for factorization of digits, and increase the speed of calculations for factors of different lengths by replacing the square root extraction and squaring at each iteration with computationally simple addition and subtraction operations. A three-module Rabin’s
cryptosystem was developed, which allowed to increase the speed of encryption and decryption processes compared to the usual integer form and to expand the encryption block without reducing the stability of the cryptosystem due to the generalization of the methods for constructing MPF RNS and their using. Also we have discovered the methodology of multi-digit numbers processing, which, through the use of matrix and vector-modular methods for finding the remainder, modular multiplication and exponentiation, finding the inverse element by adding a module or remainder, and also using the PF and MPF RNS, allowed to reduce the computational complexity and improve performance algorithms, specialized software and hardware in asymmetric cryptosystems. The application of presented methodology makes its possible to use the developed methods in a universal strategy for multi-digit numbers processing in the field of asymmetric cryptosystems and to efficiently build of highspeed cryptographic information protection systems.
