Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On orders of optimal normal basis generators

Authors: Shuhong Gao and Scott A. Vanstone
Journal: Math. Comp. 64 (1995), 1227-1233
MSC: Primary 11T30; Secondary 11Y05, 11Y16
MathSciNet review: 1297469
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we give some experimental results on the multiplicative orders of optimal normal basis generators in ${F_{{2^n}}}$ over ${F_2}$ for $n \leq 1200$ whenever the complete factorization of ${2^n} - 1$ is known. Our results show that a subclass of optimal normal basis generators always have high multiplicative orders, at least $O(({2^n} - 1)/n)$, and are very often primitive. For a given optimal normal basis generator $\alpha$ in ${F_{{2^n}}}$ and an arbitrary integer e, we show that ${\alpha ^e}$ can be computed in $O(n \cdot v(e))$ bit operations, where $v(e)$ is the number of 1’s in the binary representation of e.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T30, 11Y05, 11Y16

Retrieve articles in all journals with MSC: 11T30, 11Y05, 11Y16

Additional Information

Keywords: Finite fields, primitive elements, normal bases
Article copyright: © Copyright 1995 American Mathematical Society