Recently, pairing-based cryptographic application sch-emes have attracted much attentions. In order to make the schemes more efficient, not only pairing algorithm but also arithmetic operations in extension field need to be efficient. For this purpose, the authors have proposed a series of cyclic vector multiplication algorithms (CVMAs) corresponding to the adopted bases such as type-I optimal normal basis (ONB). Note here that every basis adapted for the conventional CVMAs are just special classes of Gauss period normal bases (GNBs). In general, GNB is characterized with a certain positive integer h in addition to characteristic p and extension degree m, namely type-⟨h.m⟩ GNB in extension field Fpm. The parameter h needs to satisfy some conditions and such a positive integer h infinitely exists. From the viewpoint of the calculation cost of CVMA, it is preferred to be small. Thus, the minimal one denoted by hmin will be adapted. This paper focuses on two remaining problems: 1) CVMA has not been expanded for general GNBs yet and 2) the minimal hmin sometimes becomes large and it causes an inefficient case. First, this paper expands CVMA for general GNBs. It will improve some critical cases with large hmin reported in the conventional works. After that, this paper shows a theorem that, for a fixed prime number r, other prime numbers modulo r uniformly distribute between 1 to r-1. Then, based on this theorem, the existence probability of type-⟨hmin,m⟩ GNB in Fpm and also the expected value of hmin are explicitly given.

It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log 2r/(k), where () is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log 2r⌋ to ⌊ log 2(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable "χ." For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log 2χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.

In this paper, a multiplication algorithm in extension field Fpm is proposed. Different from the previous works, the proposed algorithm can be applied for an arbitrary pair of characteristic p and extension degree m only except for the case when 4p divides m(p-1) and m is an even number. As written in the title, when p>m, 4p does not divide m(p-1). The proposed algorithm is derived by modifying cyclic vector multiplication algorithm (CVMA). We adopt a special class of Gauss period normal bases. At first in this paper, it is formulated as an algorithm and the calculation cost of the modified algorithm is evaluated. Then, compared to those of the previous works, some experimental results are shown. Finally, it is shown that the proposed algorithm is sufficient practical when extension degree m is small.