Basis Translation Matrix between Two Isomorphic Extension Fields via Optimal Normal Basis

다국어 초록 (Multilingual Abstract)

This paper proposes a method for generating a basis
translation matrix between isomorphic extension fields. To
generate a basis translation matrix, we need the equality
correspondence of a basis between the isomorphic
extension fields. Consider an extension field Fpm where p is
characteristic. As a brute force method, when pm is small,
we can check the equality correspondence by using the
minimal polynomial of a basis element; however, when pm
is large, it becomes too difficult. The proposed methods are
based on the fact that Type I and Type II optimal normal
bases (ONBs) can be easily identified in each isomorphic
extension field. The proposed methods efficiently use Type
I and Type II ONBs and can generate a pair of basis
translation matrices within 15 ms on Pentium 4 (3.6 GHz)
when mlog2 p = 160.

참고문헌 (Reference)

1 A. Lenstra, "The XTR Public Key System" Springer 1-19, 2000

2 K. Aoki, "Optimization of Prime Field Multiplication Using Redundant Representation" SCIS 3A3-3A5, 2004

3 D. Bailey, "Optimal Extension Fields for Fast Arithmetic on Public-Key Algorithms" 472-485, 1998

4 R.M. Avanzi, "Generic Efficient Arithmetic Algorithms for PAFFs (Processor Adequate Finite Fields)" 3006 : 321-334, 2004

5 R. Lidl, "Finite Fields, Encyclopedia of Mathematics and Its Applications" Cambridge University Press 1984

6 Y. Nogami, "Finite Extension Field with Modulus of All-One Polynomial and Representation of Its Elements for Fast Arithmetic Operations" E86–A (E86–A): 2376-2387, 2003

7 H.W. Lenstra Jr, "Finding Isomorphisms between Finite Fields" 56 : 329-347, 1991

8 Y. Nogami, "Fast Implementation of Extension Fields with Type II ONB and Cyclic Vector Multiplication Algorithm" E88–A (E88–A): 1200-1208, 2005

9 I. Blake, "Elliptic Curve in Cryptography" Cambridge University Press 1999

10 C. Paar, "Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields" Univ. of Essen 1994

11 T. Sugimura, "Consideration on Irreducible Cyclotomic Polynomials" J73–A (J73–A): 1929-1935, 1990

12 A. Menezes, "Applications of Finite Fields" Kluwer Academic Publishers 1993

13 B. Sunar, "An Efficient Basis Conversion Algorithm for Composite Fields with Given Representations" 54 (54): 992-997, 2005

14 D.G. Cantor, "A New Algorithm for Factoring Polynomials over Finite Fields" 36 : 587-592, 1981

15 V. Shoup, "A Library for Doing Number Theory"

16 T. Itoh, "A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases" 78 : 171-177, 1988