A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)

Constructing normal bases of GF(qⁿ) over GF (q) can be done by probabilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the best complexity for probabilistic algorithms is O(n² log⁴n log² (log n) + n log n log (log n) log q ) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of Xⁿ - 1 over GF(q). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is O(n³ log n log(log n) + n² log n log(log n) log q). For other deterministic constructions, which need such a factorization, the best complexities are O(n^3,376 + n² log n log(log n) log q) (von zur Gathen and Giesbrecht, 1990), or O(n³ log q); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of Xⁿ - 1. Its complexity is reduced to O (n³ + n log n log(log n) log q ).