
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.

Finite Extension Field with Modulus of AllOne Polynomial and Representation of Its Elements for Fast Arithmetic Operations
Yasuyuki NOGAMI Akinori SAITO Yoshitaka MORIKAWA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.9
pp.23762387 Publication Date: 2003/09/01 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Information Theory Keyword: optimal extension field, Frobenius mapping, normal basis, inversion,
Full Text: PDF(328.7KB)>>
Summary:
In many cryptographic applications, a largeorder finite field is used as a definition field, and accordingly, many researches on a fast implementation of such a largeorder extension field are reported. This paper proposes a definition field F_{p}m with its characteristic p a pseudo Mersenne number, the modular polynomial f(x) an irreducible allone polynomial (AOP), and using a suitable basis. In this paper, we refer to this extension field as an allone polynomial field (AOPF) and to its basis as pseudo polynomial basis (PPB). Among basic arithmetic operations in AOPF, a multiplication between nonzero elements and an inversion of a nonzero element are especially timeconsuming. As a fast realization of the former, we propose cyclic vector multiplication algorithm (CVMA), which can be used for possible extension degree m and exploit a symmetric structure of multiplicands in order to reduce the number of operations. Accordingly, CVMA attains a 50% reduction of the number of scalar multiplications as compared to the usually adopted vector multiplication procedure. For fast realization of inversion, we use the ItohTsujii algorithm (ITA) accompanied with Frobenius mapping (FM). Since this paper adopts the PPB, FM can be performed without any calculations. In addition to this feature, ITA over AOPF can be composed with self reciprocal vectors, and by using CVMA this fact can also save computation cost for inversion.

