Several methods for finding a basis conversion matrix between two different bases in an extension field 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 , some inefficient cases in which the towering degree 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 , but instead uses a certain polynomial basis in derived by a certain small cyclic group in . This causes re- laxation of the condition for the towering degree . In addition, our experimental results show that the proposed method substantially accelerates the computation time for finding a basis conversion matrix.