On orders of optimal normal basis generators

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.