Subquadratic Space Complexity Multiplier for GF(2n) Using Type 4 Gaussian Normal Bases

摘要

Subquadratic space complexity multipliers for optimal normal bases (ONBs) have been proposed for practical applications. However, for the Gaussian normal basis (GNB) of type t > 2 as well as the normal basis (NB), there is no known subquadratic space complexity multiplier. In this paper, we propose the first subquadratic space complexity multipliers for the type 4 GNB. The idea is based on the fact that the finite field GF(2n) with the type 4 GNB can be embedded into fields with an ONB.