Thesis is devoted to solving the scientific and practical task of research and development new methods of arithmetic transformations over large integers with delayed carry for increasing implementation of cryptographic transformations that take place in information and telecommunication systems of certification authorities in national public key infrastructure of Ukraine. The national PKI regulates the use of a qualified electronic signature according to the algorithms of DSTU 4145-2002, ECDSA, DSA and RSA. Operations of creating and verifying electronic signature are based on various mathematical methods: transformation in a ring of integers, field of integers and polynomials, in a group of points of an elliptic curve. All these transformations are impossible without arithmetic operations on integers. In this work proposed the method of integer representation with delayed carry, which due to the possibility of postponing carry operation from higher to lower words and the loan operation from lower to higher words, eliminates the interdependence between machine words when performing arithmetic operations. Performing operations with integers in the DCF representation, the processor operates with machine words in which two blocks are allocated to store the carry bits and to store the information bits. To convert a binary number to DCF it is necessary to reserve in the machine word r-bits for carry, and the remaining v-bits are filled with bits from the integer in a binary form. To convert a number from a DCF representation to a binary form, it is necessary to adjust carry (iteratively apply the carry from the lower machine word to the higher). To perform operations with integers in the DCF representation, it is necessary to modify the algorithms of arithmetic operations. Improved methods of arithmetic operations – addition,
subtraction, left shift, right shift, multiplication, squaring, modular reduction, division and comparison, which by using integers in the delayed carry representation can increase the speed of operations in fields and rings of integers. The use of delayed carry allows to apply some approaches of parallelization for methods of arithmetic operations, for example, multiplication, squaring and modular reduction. In these
operations, there is a multiplication operation, which consists of two multiplication cycles that can be parallelized. The first approach involves the parallel execution of the first and second multiplication cycles with subsequent adjustment of the results in two threads. The second approach involves the parallel execution of iterations of the first and the second multiplication cycles, followed by the merging of intermediate results, using multiple parallel threads. Proposed the methods of arithmetic operations of multiplication, squaring and modular reduction of large
integers with delayed carry and parallelization in two or multiple threads.
