A Comparative Analysis of Calculations Performed Using Combinations of Different Bases of Finite Fields

Abstract

The article is devoted to a comparative analysis of the complexity of algorithms for carrying out inversion, exponentiation in the fields of characteristic two, Tate pairing operation, and final exponentiation on a supersingular elliptic curve over these fields, taking into account the possibility of using different bases of finite fields in which the calculations are carried out. The polynomial basis (p.b) of the field, an almost p.b. (a.p.b.), the optimal normal basis (o.n.b.), and the permutated o.n.b. (p.o.n.b) basis of the field, the generator of the 2nd type or 3rd type o.n.b., as well as the duplicated a.p.b. and the duplicated p.o.n.b., and transformations of these bases are used. Multiplication in the ring implemented using a sequential multiplication program according toKaratsuba’s algorithm is applied. The operations of multiplication, exponentiation to powerand inversion in the field are considered with the use of these bases and this operation. It is shown that exponentiation to power for inversion according to Fermat’s small theorem can be implemented using 12 multiplications at insignificant expenditures for squaring. At the same time, inversion using a modification of the extended Euclidean algorithm requires a significantly fewer number of elementary operations ⊕,& and bit assignments or even only logical operations in comparison with the exponentiation by Fermat, which is confirmed by the average data on 100 executions of the inversion operation. The operations of pairing and final exponentiation are implemented in the 4th degree extension of the field using its 1st type o.n.b. or p.b. with p.b., a.p.b or p.o.n.b of the initial field. It is shown that, if for the multiplication of polynomials of degree 190 in the ring a sequential program according to the Karatsuba method is used, the p.o.n.b. of the field and the p.b. of its expansion constitute the best combination for pairing in the cryptographically significant field. In carrying out multiplication using the record beatingprogram (in the number of executable logic operations),the combination involving the p.b. of the main field and the o.n.b. of the 1st type of its expansion is more preferable. However, a significant advantage of the final exponentiation inthe p.o.n.b. of the main field and o.n.b. of the 1st type of its expansion entails the advantage of using this basis of the main field both in pairing, and in the final exponentiation, and for the effective implementation of the next operation of the final exponentiation after the pairing operation,it is necessary to make conversion from the p.b. to o.n.b. extension of the field,which is implemented quite easily by using the minimal polynomial common for thep.b. and o.n.b.. Then, the final exponentiation is performed by carrying out 17 multiplications in the field extension at almost negligible cost of squaring in intermediate computations. The results are obtained by analyzing primary sources, algorithms, and via computer experiments.