Fast Deterministic Normal Bases and Circulant Polynomial Determinants

Abstract

Let $\mathsf{E}={\mathbb{F}}_q[x]/(\Gamma )$ describe an algebraic extension of a finite field ${\mathbb{F}}_q$, where $q$ is a prime power and $\Gamma \in {\mathbb{F}}_q[x]$ is monic and irreducible of degree $n$. We give a deterministic algorithm that finds $\beta \in \mathsf{E}$ whose conjugates $\beta ,{\beta }^q,\dots ,{\beta }^{q^{n-1}}$ form an ${\mathbb{F}}_q$-basis of $\mathsf{E}/{\mathbb{F}}_q$, a normal basis, using $O_{\epsilon }((n^2\log q{)}^{1+\epsilon })+O\stackrel{~}{}(n{\log }^{2}q)$ bit operations for any $\epsilon >0$. For $n>1$, let $\theta =x\mathrm{mod}\Gamma$, so $\mathsf{E}={\mathbb{F}}_q[\theta ]$. A variant of a construction of Artin shows that ${\beta }_t=(\theta -t{)}^{-1}$ is normal for all but at most $n(n-1)$ parameters $t\in {\mathbb{F}}_q$. We present an algorithm to construct an $n\times n$ circulant matrix over ${\mathbb{F}}_q[\mathcal{T}]$, for an indeterminate $\mathcal{T}$, whose determinant at $\mathcal{T}=t$ is non-zero precisely when ${\beta }_t$ is normal, and show this algorithm requires $O\stackrel{~}{}(n^2+n\log q)$ operations in ${\mathbb{F}}_q$. Then, as a primary subroutine, using triangular-set power projection and modular composition, we show how to compute the determinant of any $n\times n$ circulant over ${\mathbb{F}}_q[\mathcal{T}]$, given by its first row of polynomials of degree at most $m\ge 1$, using $O_{\epsilon }((nm\log q{)}^{1+\epsilon })$ bit operations. For $q\le n(n-1)$, we show how to embed our problem into a sufficiently large field extension, construct a normal basis there, and descend to the ground field, within the same stated cost.