ON ORDERS OF OPTIMAL NORMAL BASIS GENERATORS

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 less than or equal to 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 . v(e)) bit operations, where v(e) is the number of 1's in the binary representation of e.