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 ${BBF _{p^{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 ${BBF _{(p^{m})^{n}}}$, 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 ${BBF _{p^{m}}}$, but instead uses a certain polynomial basis in ${BBF _{p^{m}}}$ derived by a certain small cyclic group in ${BBF _{(p^{m})^{n}}}$. 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.