Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

PII: S 0025-5718(1995)1297469-6
Keywords: Finite fields, primitive elements, normal bases
Article copyright: © Copyright 1995 American Mathematical Society