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

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 F_p^m where p is characteristic. As a brute force method, when p^m is small, we can check the equality correspondence by using the minimal polynomial of a basis element; however, when p^m 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 mlog₂ p = 160.