Let double-struck F signq be a finite field and consider an extension double-struck F signqn where an optimal normal element exists. Using the trace of an optimal normal element in double-struck F signqn , we provide low complexity normal elements in double-struck F signq m , with m = n/k. We give theorems for Type I and Type II optimal normal elements. When Type I normal elements are used with m = n/2, m odd and q even, our construction gives Type II optimal normal elements in double-struck F signq m ; otherwise we give low complexity normal elements. Since optimal normal elements do not exist for every extension degree m of every finite field double-struck F signq , our results could have a practical impact in expanding the available extension degrees for fast arithmetic using normal bases.

Additional Metadata
Keywords Dual basis, Finite fields, Low complexity, Normal basis
Persistent URL dx.doi.org/10.1007/s10623-008-9195-5
Journal Designs, Codes and Cryptography
Christopoulou, M. (Maria), Garefalakis, T. (Theo), Panario, D, & Thomson, D. (David). (2008). The trace of an optimal normal element and low complexity normal bases. Designs, Codes and Cryptography, 49(1-3), 199–215. doi:10.1007/s10623-008-9195-5