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

✍ Scribed by Alain Poli

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 385 KB
• Volume: 19
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1995.1019

✦ Synopsis

Constructing normal bases of (G F\left(q^{n}\right)) over (G F(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\left(n^{2} \log ^{4} n \log ^{2}(\log n)+n \log n \log (\log n) \log q\right)) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of (X^{n}-1) over (G F(q)). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is (O\left(n^{3} \log n \log (\log n)+n^{2} \log n \log (\log n)\right.) (\log q)). For other deterministic constructions, which need such a factorization, the best complexities are (O\left(n^{3,376}+n^{2} \log n \log (\log n) \log q\right)) (von zur Gathen and Giesbrecht, 1990), or (O\left(n^{3} \log q\right)); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of (X^{n}-1). Its complexity is reduced to (O\left(n^{3}+n \log n \log (\log n) \log q\right)).