A DETERMINISTIC CONSTRUCTION OF NORMAL BASES WITH COMPLEXITY O(N(3)-NLOG(LOG-N) LOG-Q)(N LOG)

Constructing normal bases of GF(q(n)) over GF(q) can be done by probab ilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the b est complexity for probabilistic algorithms is O(n(2) log(4) n log(2) (log n) + n log n log(log n) log q) (see von zur Gathen and Shoup, 199 2). For deterministic constructions, some prior ones, e.g. Lueneburg ( 1986), do not use the factorization of X(n) - 1 over GF(q). As analyse d by Bach, Driscoll and Shallit (1993), the best complexity (from Luen eburg, 1986) is O(n(3) log n log(log n) + n(2) log n log(log n) log q) . For other deterministic constructions, which need such a factorizati on, the best complexities are O(n(3,376) + n(2) log n log(log n) log q ) (von zur Gathen and Giesbrecht, 1990), or O(n(3) log q); see Augot a nd Camion (1993). Here we propose a new deterministic construction tha t does not require the factorization of X(n) - 1. Its complexity is re duced to O(n(3) + n log n log(log n) log q).