
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Cyclic Vector Multiplication Algorithm and Existence Probability of Gauss Period Normal Basis
Kenta NEKADO Yasuyuki NOGAMI Hidehiro KATO Yoshitaka MORIKAWA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E94A
No.1
pp.172179 Publication Date: 2011/01/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E94.A.172 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Mathematics Keyword: extension field, Gauss period normal basis, all one polynomial field, cyclic vector multiplication algorithm,
Full Text: PDF(788.7KB)>>
Summary:
Recently, pairingbased cryptographic application schemes 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 typeI 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 F_{pm}. 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 h_{min} will be adapted. This paper focuses on two remaining problems: 1) CVMA has not been expanded for general GNBs yet and 2) the minimal h_{min} 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 h_{min} 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 r1. Then, based on this theorem, the existence probability of type⟨h_{min},m⟩ GNB in F_{pm} and also the expected value of h_{min} are explicitly given.

