Onai M. Methods and Means of Implementation Efficiency Increasing for Computational Operations in Finite Fields

The thesis is devoted to the problem of increasing the efficiency of computations in finite fields. The proposed solution to this problem is to develop methods and means for performing operations on elements of finite fields GF(p) or GF(2m). The analysis of the current state of the development of methods of operations in finite fields is carried out and priority points are highlighted. It is best to classify them on the basis of the distinguished features. The classification of the methods of performing the most computational expensive operations (the calculation of the multiplicative inverse element and the exponentiation) in the finite fields was per-formed. It enables to conduct thorough research and form the directions of develop-ment for these methods. The method of high-speed implementation of additive and multiplicative opera-tions on elements of GF(2m) and corresponding hardware structures for its implemen-tation are proposed. Additive operations include addition and subtraction. Multiplica-tive operations include multiplication, exponentiation, multiplicative inverse element calculation, and division. The research has shown that table storage of elements of the GF(2m) in their polynomial and power representation ensures the maximum speed and versatility of the arithmetic logic unit. With the use of long integer operands, the sparse formation of the table of field elements is proposed. It enables reducing the memory consumption for its storage in several times. The algorithms for converting power representation into polynomial one and polynomial representation in power one with the use of a sparse table are constructed. The developed method provides a 15% increase in performance comparing with the existing method. The research of the developed Galois processor has been carried out, which showed that this processor provides an increase in the productivity of computing by 27% compared with the universal computing means. A program model of the Galois processor is constructed, which allows the user to create software of arbitrary complexity in Assembler of the Galois processor.