A Multiplication Algorithm in Fpm Such That p>m with a Special Class of Gauss Period Normal Bases

Hidehiro KATO  Yasuyuki NOGAMI  Tomoki YOSHIDA  Yoshitaka MORIKAWA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E92-A  No.1  pp.173-181
Publication Date: 2009/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Mathematics
Keyword: 
extension field,  public-key cryptography,  fast implementation,  Gauss period normal bases,  optimal normal basis, 

Full Text: PDF(215.8KB)

Summary: 
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.