Finding a basis conversion matrix using a polynomial basis derived by a small multiplicative cyclic group

Several methods for finding a basis conversion matrix between two different bases in an extension field Fp ^m have been proposed. Among them, the one based on Gauss period normal basis (GNB) is on average the most efficient. However, since it needs to construct a certain tower field F(p ^m) ⁿ, some inefficient cases in which the towering degree n becomes large have been reported. This paper first determines that such inefficient cases are caused by the GNB condition. In order to overcome this inefficiency, we propose a method that does not use any GNB in the target extension field Fp ^m, but instead uses a certain polynomial basis in Fp ^m derived by a certain small cyclic group in F(p ^m) ⁿ. This causes relaxation of the condition for the towering degree n. In addition, our experimental results show that the proposed method substantially accelerates the computation time for finding a basis conversion matrix.