July 01, 2026
Let \({\mathsf{E}}=\mathbb{F}_q[x]/(\Gamma)\) be an algebraic extension of degree \(n\) over the finite field \(\mathbb{F}_q\), given by a \(\Gamma\in\mathbb{F}_q[x]\) monic and irreducible. It is classical that any such \({\mathsf{E}}\) contains an element \(\beta\in{\mathsf{E}}\) that is normal over \(\mathbb{F}_q\), i.e., the conjugates \(\beta,\beta^q,\ldots,\beta^{q^{n-1}}\) form an \(\mathbb{F}_q\)-basis of \({\mathsf{E}}\) over \(\mathbb{F}_q\). In this paper we give a deterministic algorithm which finds such a normal element using \(O_\epsilon((n^2\log q)^{1+\epsilon})+{O\,\tilde{}\,}(n\log^2 q)\) bit operations, for any \(\epsilon>0\).
The algorithm works by showing that, for a parameter \(t\in\mathbb{F}_q\), the element \(\beta_t=(\theta-t)^{-1}\) is normal except for at most \(n(n-1)\) values of \(t\). This is established by constructing a “cleared Moore” circulant matrix over \(\mathbb{F}_{q^n}[{\mathcal{T}}]\), whose determinant degree at most \(n(n-1)\), such that \(\beta_t\) is normal if and only the determinant is non-zero at \(t\in\mathbb{F}_q\). For faster computation over the base field, we replace this by an equivalent trace Gram circulant matrix over \(\mathbb{F}_q[{\mathcal{T}}]\).
A main algorithmic contribution is a fast determinant algorithm for circulant matrices of polynomials, which uses triangular set projection and modular composition techniques to achieve a near-linear cost. Given an \(n\times n\) circulant matrix over \(\mathbb{F}_q[t]\) whose entries have degree at most \(m>0\), we show how to compute its determinant deterministically with \(O_\epsilon((nm\log q)^{1+\epsilon})\) bit operations.
We complete the solution by showing how to extend this to finite fields of size less than \(n(n-1)\), through an embedding in a low-degree extension field, at poly-logarithmic additional cost.
Let \(\mathbb{F}_q\) be the finite field with \(q\) elements. A finite extension field \({\mathsf{E}}=\mathbb{F}_q[x]/(\Gamma)\cong\mathbb{F}_{q^n}\) is constructed via a monic irreducible polynomial \(\Gamma\in\mathbb{F}_q[x]\) of degree \(n\). A normal basis of \({\mathsf{E}}/\mathbb{F}_q\) is a \(\mathbb{F}_q\)-basis of the form \[\{\beta,\beta^q,\ldots,\beta^{q^{n-1}}\} \subseteq {\mathsf{E}}\] for some normal element \(\beta\in{\mathsf{E}}\). It is an important classical result that a normal element \(\beta\) always exists. Our goal here is to construct such an element deterministically in nearly quadratic time with respect to \(n\).
Normal bases have a number of computational advantages over other bases, such as the power basis for finite field arithmetic. The most fundamental is that the \(q\)th-power Frobenius automorphism acts as a cyclic shift on the coordinates of any element represented in a normal basis, making the exponentiation by power of \(q\) essentially free. This makes normal bases attractive in cryptographic applications over binary fields, where they underpin efficient hardware multipliers for elliptic curve cryptography [1]. The same Frobenius shift property makes them useful in algorithms for factoring polynomials over finite fields, where manipulating the Frobenius map efficiently is central [2], [3]. Normal bases are also a key ingredient in algorithms for computing isomorphisms and embeddings between finite fields. The deterministic polynomial-time algorithm [4] constructs a normal basis as an essential subroutine, and subsequent work [5] has continued to rely on this approach. Normal bases further arise in the study of linear-feedback shift registers, in the construction of optimal codes, and in algorithms for computing Frobenius forms of matrices over finite fields [2], [6].
The deterministic construction of normal bases has a long history [4], [7], [8]. Augot & Camion [9] give a deterministic linear algebra construction requiring \(O(n^3+n^2\log q)\) operations in \(\mathbb{F}_q\). See Gao [10]. Deterministic Krylov and Frobenius-form methods [6], [11] can be employed to reduce the deterministic cost to \({O\,\tilde{}\,}(n^\omega+n^2\log q)\) operations in \(\mathbb{F}_q\), where \(\omega\) is the exponent of matrix multiplication (the best known \(\omega\approx 2.371339\) [12]).
Randomized algorithms are faster in many settings. The Las Vegas algorithms of [13] construct elements of prescribed additive order, and hence normal elements, by sampling and testing. The fast Frobenius and modular-composition techniques of [3], together with later fast modular-composition work such as [14], provide important arithmetic primitives for this approach. Building on these, [15], [16] developed related Las Vegas constructions for normal elements and normal bases in abelian and metacyclic extensions.
A basic distinction is between constructing one normal element and explicitly writing the whole normal basis. A normal element in the input power basis has output size \(n\), whereas the full list of conjugates, or a conversion matrix between the power basis and the normal basis, has output size \(n^2\). Thus quadratic time is the natural output-size barrier for explicit bases; note that conversion between the power basis and a normal basis can be done in randomized subquadratic time [3], [14]. Once a normal element is known, the full normal basis can be written out deterministically in essentially quadratic time as well, as its conjugates form a Frobenius orbit computable by the iterated Frobenius method of von zur Gathen & Shoup [2].
Although an algebraic cost model, counting \(\mathbb{F}_q\)-operations at unit cost, would be preferable, our complexity goals appear out of reach there: some core operations rest on the modular composition algorithm of Kedlaya & Umans [14] and are analyzed over a boolean RAM, so we state all costs in bit operations.
We reduce the construction of a normal element \(\beta\) to the computation of a size-\(n\) circulant determinant with polynomial entries over \({\mathbb{F}}_q\), and we prove that in general, such a determinant can be computed in near-linear time in its natural input/output size. In the normal-basis application, this size is \(O(n^2)\), resulting in an essentially quadratic bound \[\label{eq:complexity} O_\epsilon((n^2\log q)^{1+\epsilon})+{O\,\tilde{}\,}(n\log^2 q)\tag{1}\] bit operations for the whole procedure, for any fixed \(\epsilon > 0\) (here, the soft-O notation \({O\,\tilde{}\,}\) indicates the omission of polylogarithmic factors). The bottleneck is a triangular power-projection primitive described in Section 4.3. If we could strengthen its runtime to truly softly-linear, the same reduction would immediately apply to our main result.
The algorithm proceeds as follows. Let \(\theta = x\bmod \Gamma\) be the image of \(x\) in \({\mathsf{E}}\). For any \(t\in\mathbb{F}_q\) define \[\beta_t=(\theta-t)^{-1}\in{\mathsf{E}}.\] If we write the conjugates of \(\theta\) as \(\theta_i=\theta^{q^i}\in{\mathsf{E}}\), then the conjugates of \(\beta_t\) have the form \((\theta_i-t)^{-1}\). The Moore determinant criterion [17] says that \(\beta_t\) is normal if and only if the determinant of its Moore matrix — wherein the \(i\)th row consists of the successive conjugates of \((\theta_i-t)^{-1}\) — is nonzero. After a suitable row permutation and clearing some denominators, this Moore matrix becomes a circulant matrix over \({\mathsf{E}}\) with entries that depend polynomially on \(t\). Seeing the determinant of this matrix as a polynomial in \({\mathsf{E}}[{\mathcal{T}}]\), for a new indeterminate \({\mathcal{T}}\), we prove that all choices of \(\beta_t\) are normal elements, except at most \(n(n-1)\). We point out that the family \(\beta_t = (\theta - t)^{-1}\) is closely related to the elements used in Artin’s classical proof of the normal basis theorem [10], [18], [19]. Normality fails only for values of \(t\) that are roots of a nonzero polynomial of degree at most \(n(n-1)\) in \(t\), giving the same bound on the number of bad parameters. Our choice of \((\theta-t)^{-1}\) leads us to a circulant matrix over \({\mathsf{E}}[{\mathcal{T}}]\), whose evaluation at \({\mathcal{T}}=\theta\) still has entries in \({\mathsf{E}}\); Artin’s construction also results in a matrix over \({\mathsf{E}}[{\mathcal{T}}]\), but its evaluation at \(\theta\) yields a permutation matrix, giving a somewhat cleaner proof.
A Moore matrix with entries in \({\mathsf{E}}[{\mathcal{T}}]\) is too costly to work with. Instead, we use the equivalent trace Gram matrix. This is a circulant matrix with entries \(g_0({\mathcal{T}}),\ldots,g_{n-1}({\mathcal{T}})\) that are polynomials over our base field \(\mathbb{F}_q\), and normality of \(\beta_t\) is detected by the polynomial \[D({\mathcal{T}})=\det\mathop{\mathrm{Circ}}(g_0({\mathcal{T}}),\ldots,g_{n-1}({\mathcal{T}}))\in\mathbb{F}_q[{\mathcal{T}}].\] We show that \(D\) is nonzero, and that for \(t\in\mathbb{F}_q\), \(D(t) \ne 0\) if and only if \(\beta_t\) is a normal element; in particular, \(D\) has at most \(n(n-1)\) roots in \({\mathbb{F}}_q\). The polynomials \(g_i\) have degree at most \(2n-2\), so \(D\) itself has degree at most \(2n(n-1)\). In those cases where \(q>n(n-1)\), this gives us a way of constructing a normal element once \(D({\mathcal{T}})\) is known, by evaluating it at \(n(n-1)+1\) elements in \({\mathbb{F}}_q\).
The polynomial \(D({\mathcal{T}})\) can be seen as the cyclic resultant \(\mathop{\mathrm{Res}}_z(z^n-1,A(z,{\mathcal{T}}))\in\mathbb{F}_q[{\mathcal{T}}]\) for a polynomial \(A\) of degree less than \(n\) in \(z\) and at most \(2n-2\) in \({\mathcal{T}}\), built from \(g_0,\dots,g_{n-1}\). The second part of this paper gives a deterministic algorithm for computing such determinants with near linear time in the input/output size (in general \(O(nm)\)), with \(m=\deg_{\mathcal{T}}A\geq 1\).
The paper is organized as follows. Section 2 fixes notation and recalls the trace, Moore, and circulant criteria we rely upon. Section 3 establishes the circulant criterion for normality: it constructs the trace Gram circulant, bounds the number of bad parameters by \(n(n-1)\), and reduces the construction of a normal element to a single circulant determinant. Section 4 gives the deterministic near-linear-time algorithm for this polynomial circulant matrix determinant; along the way it handles the case \(p\mid n\) through a squarefree reduction, reduces to monic inputs, and develops the fast triangular-set machinery underlying the bottleneck primitive. Finally, Section 5 removes the requirement that \(q>n(n-1)\) by passing to a small extension, constructing a normal element there, and descending it deterministically to \({\mathsf{E}}/\mathbb{F}_q\). The final near-quadratic complexity 1 is finally established in Theorem 5.
We retain the notation of the introduction: \({\mathsf{E}}=\mathbb{F}_q[x]/(\Gamma)\) with \(\Gamma\in\mathbb{F}_q[x]\) monic irreducible of degree \(n>1\), and \(\theta\) the image of \(x\) in \({\mathsf{E}}\). Let \(\sigma(a)=a^q\) be the Frobenius automorphism of \({\mathsf{E}}/\mathbb{F}_q\). Since finite fields are perfect, the extension \({\mathsf{E}}/\mathbb{F}_q\) is separable. Its trace is \(\mathop{\mathrm{Tr}}_{{\mathsf{E}}/\mathbb{F}_q}(a)=\sum_{i=0}^{n-1} \sigma^i(a),\) and the trace pairing \((a,b)\longmapsto \mathop{\mathrm{Tr}}_{{\mathsf{E}}/\mathbb{F}_q}(ab)\) is nondegenerate. We will use the standard trace-discriminant criterion: elements \(a_1,\ldots,a_n\in{\mathsf{E}}\) form an \(\mathbb{F}_q\)-basis of \({\mathsf{E}}\) if and only if \[\det\bigl(\mathop{\mathrm{Tr}}_{{\mathsf{E}}/\mathbb{F}_q}(a_i a_j)\bigr)_{1\le i,j\le n}\neq 0;\] see [1]. We also use the classical determinant criterion [17]. For elements \(a_0,\ldots,a_{n-1}\) in a finite extension of \(\mathbb{F}_q\), define the Moore matrix \[{\mathcal{M}}(a_0,\ldots,a_{n-1}) =\bigl(a_j^{q^i}\bigr)_{0\le i,j<n}.\] Then \[\det {\mathcal{M}}(a_0,\ldots,a_{n-1})\neq 0 \quad\Longleftrightarrow\quad a_0,\ldots,a_{n-1}\text{ are linearly independent over }\mathbb{F}_q.\] In particular, \(\beta\in{\mathsf{E}}\) is normal over \(\mathbb{F}_q\) if and only if the Moore determinant of \(\beta,\beta^q,\ldots,\beta^{q^{n-1}}\) is nonzero.
For a commutative ring \({\mathsf{W}}\) and elements \(a_0,\ldots,a_{n-1}\in{\mathsf{W}}\), we write \[\mathop{\mathrm{Circ}}(a_0,\ldots,a_{n-1}) = \begin{pmatrix} a_0 & \cdots & a_{n-1} \\ \vdots & \ddots & \vdots \\ a_1 & \cdots & a_0 \end{pmatrix} = \bigl(a_{s-r\bmod n}\bigr)_{0\le r,s<n} \in{\mathsf{W}}^{n\times n}\] for the corresponding circulant matrix. If \(A(z)=\sum_{i=0}^{n-1} a_i z^i,\) then \(\det\mathop{\mathrm{Circ}}(a_0,\ldots,a_{n-1})=\mathop{\mathrm{Res}}_z(z^n-1,A(z))\in{\mathsf{W}}\).
We assume standard fast polynomial arithmetic, so multiplication of polynomials of degree \(d\) over \({\mathbb{F}}_q\) costs \({O\,\tilde{}\,}(d)\) operations in \(\mathbb{F}_q\); as a consequence, arithmetic operations in \({\mathsf{E}}\) take \({O\,\tilde{}\,}(n)\) operations in \(\mathbb{F}_q\). The construction below requires all the Frobenius conjugates of the power-basis generator \(\theta\), \[\theta_i=\theta^{q^i},\qquad 0\le i<n.\] We use the iterated-Frobenius method of von zur Gathen & Shoup [2], which computes all of \(\theta_0,\ldots,\theta_{n-1}\) with \({O\,\tilde{}\,}(n^2+n\log q)\) operations in \(\mathbb{F}_q\).
In this section, we first show how to construct a normal element \(\beta_t\) for \({\mathsf{E}}/\mathbb{F}_q\) from an element \(t\in\mathbb{F}_q\) that does not cancel the determinant of a certain Moore circulant matrix \(B(T)\) over \(E[T]\). In a second stage, we introduce a circulant matrix \({G}({\mathcal{T}})\) over \(\mathbb{F}_q[{\mathcal{T}}]\), with the property that \(\det G=(\det B)^2\).
Our construction is similar to Artin’s [18]: for \(t\in\mathbb{F}_q\), let \(\beta_t=(\theta-t)^{-1}\in{\mathsf{E}}\); see [10]. This is well-defined: since \(n>1\), the irreducible polynomial \(\Gamma\) has no root in \(\mathbb{F}_q\), and so \(\Gamma(t)\neq 0\).
Write \(\theta_i=\theta^{q^i}\) for \(0\le i<n\), with indices taken modulo \(n\). The roots of \(\Gamma\) are exactly the \(\theta_i\), and hence, if we let \({\mathcal{T}}\) be a new indeterminate, we have \[\Gamma({\mathcal{T}})=\prod_{i=0}^{n-1}({\mathcal{T}}-\theta_i) \in {\mathsf{E}}[{\mathcal{T}}].\] For \(0\le i<n\), define \[b_i({\mathcal{T}})=\frac{\Gamma({\mathcal{T}})}{\theta_i-{\mathcal{T}}} =-\prod_{j\neq i}({\mathcal{T}}-\theta_j)\in{\mathsf{E}}[{\mathcal{T}}].\]
Lemma 1 (Cleared Moore circulant). Let \[B({\mathcal{T}})=\mathop{\mathrm{Circ}}(b_0({\mathcal{T}}),\ldots,b_{n-1}({\mathcal{T}}))\in{\mathsf{E}}[{\mathcal{T}}]^{n\times n}.\] Then, for every \(t\in\mathbb{F}_q\), \(\beta_t\) is normal over \(\mathbb{F}_q\) if and only if \(\det B(t)\neq 0\). Moreover, \(\det B({\mathcal{T}})\) is a nonzero polynomial in \({\mathsf{E}}[{\mathcal{T}}]\) of degree at most \(n(n-1)\).
Proof. For \(t\in\mathbb{F}_q\), the conjugates of \(\beta_t\) are \(\beta_t^{q^i}=(\theta_i-t)^{-1}\) for \(0\le i<n\). After the row permutation \(r\mapsto -r\), their Moore matrix is \[C(t)=\mathop{\mathrm{Circ}}\bigl((\theta_0-t)^{-1},\ldots, (\theta_{n-1}-t)^{-1}\bigr).\] Moore’s criterion gives normality exactly when \(\det C(t)\neq 0\). Since \(\Gamma(t)\neq 0\) and \(B(t)=\Gamma(t)C(t)\), this is equivalent to \(\det B(t)\neq 0\).
Each \(b_i\) has degree \(n-1\), so \(\deg\det B\le n(n-1)\). To prove that this determinant is not identically zero, evaluate at \({\mathcal{T}}=\theta_j\). Then \(b_i(\theta_j)=0\) for \(i\neq j\), and \(b_j(\theta_j)=-\Gamma'(\theta_j)\neq 0\), because \(\Gamma\) is separable. Thus \(B(\theta_j)\) is a nonzero scalar multiple of a cyclic permutation matrix, and so its determinant is nonzero. ◻
This immediately yields the following corollary.
Corollary 1 (Bad parameters). The set of \(t\in\mathbb{F}_q\) for which \(\beta_t\) is not normal has size at most \(n(n-1)\). In particular, if \(q>n(n-1)\), then some \((\theta-t)^{-1}\) is normal over \(\mathbb{F}_q\).
The matrix \(B\) proves the bound above, but its entries lie in \({\mathsf{E}}[{\mathcal{T}}]\). We now pass to a circulant over \(\mathbb{F}_q[{\mathcal{T}}]\) without losing any information at points of \(\mathbb{F}_q\). For \(0\le k<n\), define \[g_k({\mathcal{T}})=\sum_{i=0}^{n-1} b_i({\mathcal{T}})b_{i+k}({\mathcal{T}}),\] with indices modulo \(n\), and set \[{G}({\mathcal{T}})=\mathop{\mathrm{Circ}}(g_0({\mathcal{T}}),g_1({\mathcal{T}}),\ldots,g_{n-1}({\mathcal{T}})).\]
Lemma 2 (Cleared trace Gram circulant). The polynomials \(g_0,\ldots,g_{n-1}\) lie in \(\mathbb{F}_q[{\mathcal{T}}]\), and \[{G}({\mathcal{T}})=B({\mathcal{T}})^{\top}B({\mathcal{T}}).\] Hence, \(\det {G}({\mathcal{T}})=(\det B({\mathcal{T}}))^2\), so for every \(t\in\mathbb{F}_q\), \[\det{G}(t)\neq 0 \quad\Longleftrightarrow\quad \beta_t\text{ is normal over }\mathbb{F}_q.\] Moreover, \(\deg g_k\le 2n-2\) for all \(k\).
Proof. Extend Frobenius to \({\mathsf{E}}[{\mathcal{T}}]\) by fixing \({\mathcal{T}}\). Since \(\sigma(b_i)=b_{i+1}\), cyclic reindexing gives \[\sigma(g_k)=\sum_i b_{i+1}b_{i+k+1}=g_k.\] Thus \(g_k\in\mathbb{F}_q[{\mathcal{T}}]\). The degree bound follows from \(\deg b_i=n-1\). By the definition of a circulant matrix, \[(B^{\top}B)_{r,\ell} =\sum_{i=0}^{n-1} b_{r-i}b_{\ell-i} =\sum_{j=0}^{n-1} b_jb_{j+\ell-r} =g_{\ell-r},\] so \(B^{\top}B={G}\). Therefore \(\det{G}(t)=\det(B(t))^2\), and the equivalence with normality follows from Lemma 1. ◻
Note that for \(t\in\mathbb{F}_q\), \(\Gamma(t)^{-2}{G}(t)\) is the trace Gram matrix of the conjugates of \(\beta_t\). Indeed, if \(0\le r,\ell<n\), then \[\Gamma(t)^{-2}{G}(t)_{r,\ell} =\sum_{i=0}^{n-1} \frac{1}{(\theta_i-t)(\theta_{i+\ell-r}-t)} =\mathop{\mathrm{Tr}}_{{\mathsf{E}}/\mathbb{F}_q}\bigl(\beta_t^{q^r}\beta_t^{q^\ell}\bigr).\]
We now compute the first row of \({G}\) efficiently by the same product calculation that underlies Lagrange interpolation at the conjugates of \(\theta\). The polynomial \[\frac{\Gamma({\mathcal{T}})}{{\mathcal{T}}-\theta_i}\in\mathbb{F}_q[{\mathcal{T}}]\] vanishes at all conjugates of \(\theta\) except \(\theta_i\), where its value is \(\Gamma'(\theta_i)\). The cyclic sums used below are fixed by Frobenius and therefore lie in \(\mathbb{F}_q[T]\). Thus the needed values are obtained from \[\Gamma'(\theta)=\prod_{j=1}^{n-1}(\theta-\theta_j)\] by deleting one factor.
Lemma 3 (First row formula). Let \(\Gamma'\), \(\Gamma''\in\mathbb{F}_q[{\mathcal{T}}]\) denote first and second formal derivative of \(\Gamma\) respectively. Then \[g_0({\mathcal{T}})=\Gamma'({\mathcal{T}})^2-\Gamma({\mathcal{T}})\Gamma''({\mathcal{T}})\in\mathbb{F}_q[{\mathcal{T}}].\] For \(1\le j<n\), put \[d_j=\theta-\theta_j, \qquad h_j=\prod_{\substack{1\le m<n\\ m\neq j}} d_m\in{\mathsf{E}}.\] Empty products are understood to be \(1\). For \(1\le k<n\), let \(H_k(x)\in\mathbb{F}_q[x]\) be the representative of \(h_k+h_{n-k}\) of degree less than \(n\). Then \[g_k({\mathcal{T}})=\Gamma({\mathcal{T}})H_k({\mathcal{T}}).\] In particular, \(\deg H_k\le n-2\) and \(g_{n-k}=g_k\).
Proof. Since \[g_0({\mathcal{T}})=\Gamma({\mathcal{T}})^2 \sum_{i=0}^{n-1}\frac{1}{({\mathcal{T}}-\theta_i)^2},\] the logarithmic derivative identity \[\frac{\Gamma'({\mathcal{T}})}{\Gamma({\mathcal{T}})} =\sum_{i=0}^{n-1}\frac{1}{{\mathcal{T}}-\theta_i}\] gives, after differentiation, \[\sum_i\frac{1}{({\mathcal{T}}-\theta_i)^2} =\frac{\Gamma'({\mathcal{T}})^2-\Gamma({\mathcal{T}})\Gamma''({\mathcal{T}})}{\Gamma({\mathcal{T}})^2}.\] This proves the formula for \(g_0\).
Now let \(1\le k<n\). From the definition of \(g_k\), \[g_k({\mathcal{T}})=\Gamma({\mathcal{T}})Q_k({\mathcal{T}}), \quad where\quad Q_k({\mathcal{T}})=\sum_{i=0}^{n-1} \frac{\Gamma({\mathcal{T}})}{({\mathcal{T}}-\theta_i)({\mathcal{T}}-\theta_{i+k})}.\] Each summand is a polynomial of degree \(n-2\), and the sum is fixed by Frobenius, so \(Q_k\in\mathbb{F}_q[{\mathcal{T}}]\) and \(\deg Q_k\le n-2\).
Evaluate \(Q_k\) at \(\theta=\theta_0\). All summands vanish except those with \(i=0\) and \(i=n-k\). Hence \[Q_k(\theta) =\frac{\Gamma'(\theta)}{\theta-\theta_k} +\frac{\Gamma'(\theta)}{\theta-\theta_{n-k}}.\] Since \[\Gamma'(\theta)=\prod_{j=1}^{n-1}(\theta-\theta_j) =\prod_{j=1}^{n-1}d_j,\] this gives \[Q_k(\theta)=h_k+h_{n-k}.\] The evaluation map from polynomials of degree less than \(n\) to \({\mathsf{E}}\) is an isomorphism, so \(Q_k=H_k\). The identity \(g_{n-k}=g_k\) follows either from this formula or by reindexing the defining sum for \(g_k\). ◻
The polynomials \(g_0,\ldots,g_{n-1}\) can be computed in \({O\,\tilde{}\,}(n^2+n\log q)\) operations in \(\mathbb{F}_q\). They satisfy \(\deg g_k\le 2n-2\) for all \(k\).
Proof. Compute the Frobenius table \(\theta_0,\theta_1,\ldots,\theta_{n-1}\) by the method recalled in Section 2. This costs \({O\,\tilde{}\,}(n^2+n\log q)\) operations over \(\mathbb{F}_q\). Form \(d_j=\theta-\theta_j\) for \(1\le j<n\). Then compute all products \[h_j=\prod_{\substack{1\le m<n\\m\neq j}}d_m\] by one forward sweep and one backward sweep. Set \(L_0=1, \qquad L_j=d_1d_2\cdots d_j\quad(1\le j<n).\) Then sweep backwards with \(S=1\); at step \(j=n-1,n-2,\ldots,1\), set \[h_j=L_{j-1}S, \qquad S\leftarrow Sd_j.\] This uses \(O(n)\) multiplications in \({\mathsf{E}}\), hence \({O\,\tilde{}\,}(n^2)\) operations over \(\mathbb{F}_q\). Compute \(g_0=\Gamma'^2-\Gamma\Gamma''.\)
For \(1\le k\le \lfloor n/2\rfloor\), let \(H_k\) be the representative of \(h_k+h_{n-k}\) of degree less than \(n\), and set \[g_k=\Gamma H_k, \qquad g_{n-k}=g_k.\] If \(k=n-k\), this assignment is made only once. The products \(\Gamma H_k\) cost \({O\,\tilde{}\,}(n^2)\) operations in total. The formulas and degree bounds are those of Lemma 3. ◻
Set \[D({\mathcal{T}})=\det{G}({\mathcal{T}}) =\det\mathop{\mathrm{Circ}}(g_0({\mathcal{T}}),\ldots,g_{n-1}({\mathcal{T}}))\in\mathbb{F}_q[{\mathcal{T}}].\] For every \(t\in\mathbb{F}_q\), \(D(t)\neq 0\) if and only if \(\beta_t\) is normal over \(\mathbb{F}_q\). The degree of \(D\) may be as large as \(2n(n-1)\), but the number of bad parameters is still bounded by \(n(n-1)\), by Corollary 1.
We now isolate the remaining determinant computation.
Problem 1 (Circulant determinant). Given polynomials \(a_0({\mathcal{T}}),\ldots,a_{n-1}({\mathcal{T}})\in\mathbb{F}_q[{\mathcal{T}}]\) of degree at most \(m\), for some \(m > 0\), compute \[\det\mathop{\mathrm{Circ}}(a_0({\mathcal{T}}),a_1({\mathcal{T}}),\ldots,a_{n-1}({\mathcal{T}})).\] Equivalently, for \(A(z,{\mathcal{T}})=\sum_{i=0}^{n-1}a_i({\mathcal{T}})z^i\), compute \(\mathop{\mathrm{Res}}_z(z^n-1,A(z,{\mathcal{T}}))\).
Let \(\Phi(z)=z^n-1\). We prove the following theorem in the rest of the section.
Theorem 2 (polynomial circulant determinant). Suppose that \({\mathbb{F}}_q\) is presented as \({\mathbb{F}}_p[y]/(\Lambda(y))\), for some irreducible polynomial \(\Lambda \in {\mathbb{F}}_p[y]\). Then the polynomial \[\det C({\mathcal{T}})=\mathop{\mathrm{Res}}_z(\Phi(z),A(z,{\mathcal{T}}))\in{\mathbb{F}}_q[{\mathcal{T}}]\] can be computed using \(O_\epsilon((nm\log q)^{1+\epsilon})\) bit operations, for any \(\epsilon > 0\).
For the trace-Gram circulants constructed in Proposition [prop:buildG], one has \(m\le 2n-2\), and hence \(nm \in O(n^2)\).
If \(A\) is monic in \({\mathcal{T}}\), the problem reduces to computing the characteristic polynomial of multiplication by \({\mathcal{T}}\) in the \({\mathbb{F}}_q\)-algebra \(\mathcal{A}={\mathbb{F}}_q[z,{\mathcal{T}}]/(\Phi(z), A(z,{\mathcal{T}}))\), and \(A\) being monic allows us to use existing fast algorithms for triangular sets to conclude.
There is however no guarantee that \(A\) is monic in \({\mathcal{T}}\). The so called dynamic evaluation techniques allow us to reduce to this situation, but it requires \(\Phi\) be squarefree, which we don’t assume (this is equivalent to \(\gcd(n,p)=1\)). We handle this issue in Subsection 4.1: due to its special shape, computing the squarefree decomposition of \(\Phi\) is straightforward, and the multiplicativity of the resultant allows us to work with the squarefree part \(\varphi\) of \(\Phi\) instead of \(\Phi\) itself.
In Subsection 4.2, we reduce to the case where \(A\) is monic. The obvious idea is to divide \(A\) by its leading coefficient \(\ell\) in \({\mathcal{T}}\), working modulo \(\varphi\). However, we cannot assume that \(\varphi\) is irreducible, so \(\ell\) may have a non-trivial GCD with \(\varphi\). This gives us a factorization of \(\varphi\) into \(\gcd(\varphi,\ell)\), modulo which \(\ell\) vanishes, and \(\varphi/\gcd(\varphi,\ell)\), modulo which \(\ell\) is a unit. Continuing this process leads us to a factorization of \(\varphi\) into coprime factors \(H_1,\dots,H_s\), modulo which we can guarantee that the leading coefficient of \(A\) is invertible.
Subsection 4.3 handles the core question of computing \(\mathop{\mathrm{Res}}_z(H(z),P(z,{\mathcal{T}}))\), with \(H\) and \(P\) monic in respectively \(z\) and \({\mathcal{T}}\). We observe that this is equivalent to computing the characteristic polynomial of the endomorphism of multiplication by \({\mathcal{T}}\) modulo \((H(z),P(z,{\mathcal{T}}))\), which we proceed to handle by a version of Leverrier’s algorithm.
The first step in the whole procedure is to compute the squarefree decomposition of \(\Phi\). Write \(n=p^c r\), with \(\gcd(r,p)=1\); it follows that in \({\mathbb{F}}_q[z]\), we have \[\Phi = z^n-1 = \varphi^{p^c},\] with \(\phi=z^r-1\) squarefree. The integers \(c\) and \(r\) are computed on a Boolean RAM as follows: given the base-2 expansion of \(n\), we can obtain its base-\(p\) expansion in \({O\,\tilde{}\,}(\log n)\) bit operations [20]. From this, we deduce \(c\) and \(r\) (in base 2) in softly linear time again.
Let \(B(z,{\mathcal{T}}) = A(z,{\mathcal{T}}) \bmod \varphi\); we can compute it using \({O\,\tilde{}\,}(n m)\) operations in \({\mathbb{F}}_q\) by Euclidean division coefficientwise in \({\mathcal{T}}\). By multiplicativity of the resultant, we deduce that \[\mathop{\mathrm{Res}}_z(\Phi(z),A(z,{\mathcal{T}})) = \mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}}))^{p^c},\] so we can focus on computing \(\mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}}))\). This is a polynomial of degree at most \(r m\) in \({\mathbb{F}}_q[{\mathcal{T}}]\), and raising it to \(p^c\)-th power to obtain \(\mathop{\mathrm{Res}}_z(\Phi(z),A(z,{\mathcal{T}}))\) also takes \({O\,\tilde{}\,}(n m)\) operations in \({\mathbb{F}}_q\) by repeated squaring.
In order to compute \(\mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}}))\), the second step is to reduce to the case where \(B(z,{\mathcal{T}})\) is monic in \({\mathcal{T}}\). If \(\varphi\) were irreducible, this would amount to inverting the leading coefficient of \(B\) modulo \(\varphi\), but all we know is that \(\varphi\) is squarefree. Instead, we use the notion of monic form from [21]: a monic form for the pair \((\varphi,B)\) is a sequence \(((H_1,B_1,c_1),\dots,(H_s,B_s,c_s))\), that satisfies the following:
for all \(i\), \(H_i\) and \(c_i\) are in \({\mathbb{F}}_q[z]\), \(H_i\) is monic of positive degree and \(c_i\) is reduced with respect to \(H_i\)
\(\varphi=H_1 \cdots H_s\)
for all \(i\), \(B_i = B \bmod H_i\) in \({\mathbb{F}}_q[z,{\mathcal{T}}]\)
for all \(i\), either \(B_i=c_i=0\) or \(P_i=c_i B_i \bmod H_i\) is monic in \({\mathcal{T}}\).
Using Proposition 2.4 in [21] and Algorithm monic from that reference, a monic form can be computed in \({O\,\tilde{}\,}(r m)\) operations in \({\mathbb{F}}_q\).
Using again the multiplicativity of the resultant, we deduce that \[\mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}})) = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i(z),B(z,{\mathcal{T}})) = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i(z),B_i(z,{\mathcal{T}})).\] If any \(B_i\) vanishes, this implies that \(\mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}}))=0\), so we are done. Else, we obtain \[\mathop{\mathrm{Res}}_z(\varphi(z),B(z,{\mathcal{T}})) = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i(z), b_i(z) P_i(z,{\mathcal{T}})) =R_1 R_2\] with \(b_i\) the leading coefficient of \(B_i\) in \({\mathcal{T}}\) and where \[R_1 = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i(z), b_i(z)) \quad\text{and}\quad R_2 = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i(z), P_i(z,{\mathcal{T}}))\] Computing each scalar resultant \(\mathop{\mathrm{Res}}_z(H_i(z), b_i(z))\) is done in quasi-linear time in the degree of the corresponding \(H_i\), so it remains to compute each \(\mathop{\mathrm{Res}}_z(H_i(z), P_i(z,{\mathcal{T}}))\). If we write \(d_i = \deg_z H_i\) and \(e_i =\deg_{\mathcal{T}}P_i\), the following subsection establishes that it can be done in \(O_\epsilon((d_ie_i\log q)^{1+\epsilon})\) bit operations for any \(\epsilon > 0\).
Let \({\mathsf{R}}\) be a ring and set \[\mathcal{A}={\mathsf{R}}[z,{\mathcal{T}}]/(H(z),P(z,{\mathcal{T}})),\] where \(H\in{\mathsf{R}}[z]\) is monic of degree \(d\) and \(P\in {\mathsf{R}}[z,{\mathcal{T}}]\) is monic of degree \(e\) in \({\mathcal{T}}\), and reduced with respect to \(H\). Then \(\mathcal{A}\) is a free \({\mathsf{R}}\)-module of rank \(de\), with monomial basis \(\mathcal{B}=(z^i {\mathcal{T}}^j)_{0\le i < d, 0\le j< e}\). To any element \(\alpha\) in \(\mathcal{A}\), one associates the endomorphism \(\mu_\alpha:\mathcal{A}\to\mathcal{A}\) of multiplication by \(\alpha\); the trace \(\mathop{\mathrm{Tr}}_{\mathcal{A}/{\mathsf{R}}}(\alpha) \in {\mathsf{R}}\) and the characteristic polynomial \(\chi_{\mathcal{A}/{\mathsf{R}}}(\alpha)\in {\mathsf{R}}[{\mathcal{T}}]\) of \(\alpha\) are by definition those of \(\mu_\alpha\). By extension, the trace, resp.characteristic polynomial of \(a \in {\mathsf{R}}[z,{\mathcal{T}}]\) are defined as those of its residue class in \(\mathcal{A}\).
The following lemma is folklore; we will only need it over a field, but establishing it over an arbitrary ring takes hardly more work.
Lemma 4. \(\chi_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}}) = \mathop{\mathrm{Res}}_z(H(z),P(z,{\mathcal{T}}))\).
Proof. Write \(H=z^d + \sum_{i < d} h_i z^i\) and \(P={\mathcal{T}}^e + \sum_{i < d, j<e} p_{i,j} z^i{\mathcal{T}}^j\); let further \((\bar h_i)_{i <d}\) and \((\bar p_{i,j})_{i < d,j<e}\) be new indeterminates over \(\mathbb{Q}\), which we use as coefficients to define polynomials \(\bar H\) and \(\bar P\). Both the characteristic polynomial \(C\) of \({\mathcal{T}}\) modulo \((\bar H,\bar P)\) and the resultant \(R=\mathop{\mathrm{Res}}_z(\bar H,\bar P)\) are polynomials in \({\mathbb{Z}}[t,\bar h_i,\bar p_{i,j}]\), and \(\chi_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}})\) and \(\mathop{\mathrm{Res}}_z(H,P)\) are obtained by evaluating \(C\) and \(R\) at the coefficients \(h_i\) and \(p_{i,j}\) in \({\mathsf{R}}\). This is by construction for the characteristic polynomial, and follows from \(\bar H\) being monic in \(z\) for the resultant, as in [20].
This means that it suffices to prove the claim for the polynomials \(\bar H\) and \(\bar P\). The former splits as a product of \(d\) distinct linear factors \(\prod_{i \le d}(z-z_i)\) over an algebraic closure of its field of definition. By the Chinese Remainder theorem for the left-hand side, and multiplicativity of the resultant for the right-hand side, it suffices to consider the case where \(H=(z-z_i)\), in which case both sides of the equality are seen to be \(P(z_i,{\mathcal{T}})\). ◻
This lemma reduces the computation of the resultant \(\mathop{\mathrm{Res}}_z(H(z),P(z,{\mathcal{T}}))\) to that of the characteristic polynomial \(\chi_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}})\). This will be done by means of Leverrier’s algorithm, which relies on the Newton identities \[j c_j=-\sum_{i=1}^j c_{j-i}s_i, \qquad 1\le j\le de,\] where we write \(s_k=\mathop{\mathrm{Tr}}_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}}^k)\) for \(k \ge 0\) and \(\chi_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}}) ={\mathcal{T}}^{de}+c_1{\mathcal{T}}^{de-1}+\cdots+c_{de}.\)
Given the traces \(s_0,\dots,s_{de}\), using the recurrence above to compute the \(c_j\)’s results in a number of operations in \({\mathsf{R}}\) that is quadratic in \({de}\); a more efficient approach based on Newton iteration runs in quasi-linear time. However, both algorithms require divisions by integers up to \({de}\) in \({\mathsf{R}}\), and these integers may vanish if the characteristic of \({\mathsf{R}}\) is too small.
When we work over a finite field, though, this issue can be circumvented by working with (truncated) \(p\)-adic integers rather than finite field elements. Thus, let us from now on assume that \({\mathsf{R}}={\mathbb{F}}_q\), presented as \({\mathbb{F}}_q={\mathbb{F}}_p[y]/(\Lambda(y))\), for some irreducible polynomial \(\Lambda \in {\mathbb{F}}_p[y]\) of degree \(\kappa\). For \(K \ge 1\), define further \({\mathsf{R}}_K={\mathbb{Z}}[y]/(p^K,\tilde{\Lambda}(y))\), where \(\tilde{\Lambda}\) is an arbitrary monic lift of \(\Lambda\) to \({\mathbb{Z}}[y]\) of degree \(\kappa\).
The following fact is proved in [22] when \(\kappa=1\) (so in that case \({\mathbb{F}}_q={\mathbb{F}}_p\)), but the proof holds for an arbitrary extension degree. It states that if we work with \(p\)-adic lifts of our input polynomials, a logarithmic precision (in \({de}\)) is sufficient to allow us to compute the characteristic polynomial of \({\mathcal{T}}\) in \(\mathcal{A}\). Because this involves calculations over \({\mathsf{R}}_K\) rather than \({\mathsf{R}}={\mathbb{F}}_q\), the arithmetic complexity model is not appropriate to estimate the runtime of this operation. Instead, we measure its cost in terms of bit operations on a RAM.
Fact 3. Let \(K=\lceil \log_p({de})\rceil\), and let \(\tilde{H}\) and \(\tilde{P}\) be arbitrary lifts of \(H\) and \(P\) to respectively \({\mathsf{R}}_K[z]\) and \({\mathsf{R}}_K[z,{\mathcal{T}}]\), with still \(\tilde{H}\) monic of degree \(d\) and \(\tilde{P}\) monic of degree \(e\) in \({\mathcal{T}}\) and reduced with respect to \(\tilde{H}\). Put \(\mathcal{A}_K={\mathsf{R}}_K[z,{\mathcal{T}}]/(\tilde{H}(z),\tilde{P}(z,{\mathcal{T}}))\).
Given the traces \(\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}(1),\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}({\mathcal{T}}),\ldots,\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}({\mathcal{T}}^{de})\), one can compute \(\chi_{\mathcal{A}/{\mathsf{R}}}({\mathcal{T}})\) using \({O\,\tilde{}\,}\bigl({de} \log q)\) bit operations.
Fix \(K=\lceil \log_p({de})\rceil\) as above. Given an \({\mathsf{R}}_K\)-linear form \(\tau:\mathcal{A}_K\to{\mathsf{R}}_K\) by means of its values on the monomial basis \(\mathcal{B}\) of \(\mathcal{A}_K\), power projection asks for the sequence \(\tau(1),\tau({\mathcal{T}}),\ldots,\tau({\mathcal{T}}^{de}).\)
The reconstruction algorithm takes as input these values for \(\tau =\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}\). The trace values \(\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}\) on \(\mathcal{B}\) can be computed in a quasi-linear \({O\,\tilde{}\,}({de})\) operations in \({\mathsf{R}}_K\), using [23].
Once the traces of all basis elements are known, we use the two-variable triangular-set power projection algorithm of [24], which builds on the modular composition and power projection methods of [14]. These algorithms also require that we work with a boolean RAM. The algorithm of [24] is written for polynomials with coefficients in \({\mathsf{R}}={\mathbb{F}}_q\) rather than \({\mathsf{R}}_K\), but as pointed out in [14], [25] the techniques carry over to polynomials over \({\mathsf{R}}_K\).
Fact 4 (Triangular power projection). Let \(K\), \({\mathsf{R}}_K\), \(\tilde{H}\) and \(\tilde{P}\) and \(\mathcal{A}_K\) be as in Fact 3. The sequence \[\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}(1),\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}({\mathcal{T}}),\ldots,\mathop{\mathrm{Tr}}_{\mathcal{A}_K/{\mathsf{R}}_K}({\mathcal{T}}^{de})\] can be computed in \(O_\epsilon(({de}\log q)^{1+\epsilon})\) bit operations for any \(\epsilon > 0\).
Combining Facts 3 and 4, we obtain the following proposition.
Let \(H\in{\mathbb{F}}_q[z]\) be monic of degree \(d\) and \(P\in {\mathbb{F}}_q[z,{\mathcal{T}}]\) be monic of degree \(e\) in \({\mathcal{T}}\), and reduced with respect to \(H\), where \({\mathbb{F}}_q\) is presented as \({\mathbb{F}}_p[y]/(\Lambda(y))\), for some irreducible polynomial \(\Lambda \in {\mathbb{F}}_p[y]\).
Then the resultant \(\mathop{\mathrm{Res}}_z(H(z),P(z,{\mathcal{T}}))\) can be computed in \(O_\epsilon((de\log q)^{1+\epsilon})\) bit operations for any \(\epsilon > 0\).
We can now summarize the algorithm in the order of the preceding sections, in order to compute \(\mathop{\mathrm{Res}}_z(\Phi(z),A(z,{\mathcal{T}}))\), with \(n=\deg_z \Phi\), \(\deg_t A \le m\) for some \(m > 0\).
Write \(n=p^c r\), with \(\gcd(p,r)=1\), \(\varphi=z^r-1\) and \(B=A \bmod \varphi\). This takes \({O\,\tilde{}\,}(\log n)\) bit operations and \({O\,\tilde{}\,}(n m)\) operations in \({\mathbb{F}}_q\).
Compute a monic form \(((H_1,B_1,c_1),\dots,(H_s,B_s,c_s))\) of \((\varphi,B)\), using \({O\,\tilde{}\,}(rm)\) operations in \({\mathbb{F}}_q\)
If any of the \(B_i\)’s vanishes, return \(0\).
Compute \(R_1 = \prod_{i \le s} \mathop{\mathrm{Res}}_z(H_i,b_i)\), where for all \(i\), \(b_i\) is the leading coefficient of \(B_i\). This takes \({O\,\tilde{}\,}(n)\) operations in \({\mathbb{F}}_q\) using the half-GCD resultant algorithm [20].
For all \(i\), set \(P_i = c_i B_i \bmod H_i\) and compute \(\chi_i = \mathop{\mathrm{Res}}_z(H_i,P_i)\) using Proposition [prop:char]. The former takes \({O\,\tilde{}\,}(d_i e_i)\) operations in \({\mathbb{F}}_q\), with \(d_i = \deg_z H_i\) and \(e_i=\deg_{\mathcal{T}}P_i\), the latter \(O_\epsilon((d_ie_i\log q)^{1+\epsilon})\) bit operations for any \(\epsilon > 0\).
Since \(e_i \le m\) for all \(i\) and \(d_1 + \cdots + d_s =r\), the total is \({O\,\tilde{}\,}(rm)\) operations in \({\mathbb{F}}_q\) and \(O_\epsilon((r m\log q)^{1+\epsilon})\) bit operations.
Compute \(R_2 = \prod_{i \le s} \chi_i\) in \({\mathbb{F}}_q[{\mathcal{T}}]\); because \(R_2\) has degree at most \(r m\), this takes \({O\,\tilde{}\,}(r m)\) operations in \({\mathbb{F}}_q\), using subproduct tree techniques [20].
Return \((R_1 R_2)^{p^c}\). Because the result has degree at most \(n m\), this takes \({O\,\tilde{}\,}(n m)\) operations in \({\mathbb{F}}_q\).
Since any operation in \({\mathbb{F}}_q\) can be executed on a RAM using \({O\,\tilde{}\,}(\log q)\) bit operations, the full circulant determinant computation costs \(O_\epsilon((n m\log q)^{1+\epsilon})\) bit operations, for any \(\epsilon > 0\), proving Theorem 2.
The ingredients seen so far allow us to construct a normal element if the cardinality \(q\) of the base is large enough. By Proposition [prop:buildG], construct \(g_0,\ldots,g_{n-1}\) in \({O\,\tilde{}\,}(n^2+n\log q)\) operations over \(\mathbb{F}_q\), which is \({O\,\tilde{}\,}(n^2\log q+n\log^2 q)\) bit operations. Then, compute \(D({\mathcal{T}})=\det\mathop{\mathrm{Circ}}(g_0({\mathcal{T}}),\ldots,g_{n-1}({\mathcal{T}}))\) using the circulant determinant routine, for \(O_\epsilon((n^2 \log q)^{1+\epsilon})\) bit operations. Choose any \(n(n-1)+1\) distinct elements of \(\mathbb{F}_q\) and evaluate \(D\) at them. By Corollary 1, at least one of these values, say \(t\), satisfies \(D(t)\neq 0\). Then \((\theta-t)^{-1}\) is normal over \(\mathbb{F}_q\). The multipoint evaluation uses \({O\,\tilde{}\,}(n^2)\) operations in \(\mathbb{F}_q\), and the final inversion in \({\mathsf{E}}\) is a lower order term. The total in this case is \[O_\epsilon((n^2 \log q)^{1+\epsilon}) + {O\,\tilde{}\,}(n\log^2 q)\] bit operations.
It remains to show how to construct normal elements over small fields in this same complexity. We proceed by passing to an extension \(\mathsf L\) which is large enough for our algorithm to work, compute a normal basis there, and then descend it to a normal element in \({\mathsf{E}}/\mathbb{F}_q\). The descent is a fairly standard resolvent descent for normal bases, going back to [26] and especially [27]; see [10]. This gives a criterion that an element is normal exactly when its resolvent is a unit in the corresponding group algebra.
We start by constructing an extension of \({\mathsf{E}}\). Choose a small prime \(\ell\) such that \(q^\ell>n(n-1)\) and \(\gcd(\ell,n)=1\). It is easy to show that such an \(\ell\) can be found quickly of size \(\ell=O(\log n\log\log n)\) by simply using trial division. Let \(\mathsf L={\mathbb{F}}_{q^\ell}\). Since \(\gcd(\ell,n)=1\), the polynomial \(\Gamma\in\mathbb{F}_q[x]\) remains irreducible over \(\mathsf L\). We set \({\mathsf{K}}=\mathsf L[x]/(\Gamma)\simeq {\mathbb{F}}_{q^{n\ell}}\), and view \({\mathsf{E}}=\mathbb{F}_q[x]/(\Gamma)\) as a subfield of \({\mathsf{K}}\). The fields form the following diagram: \[\begin{array}{ccccc} && {\mathsf{K}}=\mathsf L[x]/(\Gamma)\simeq{\mathbb{F}}_{q^{n\ell}} && \\[-1mm] & \swarrow && \searrow & \\[-1mm] \mathsf L={\mathbb{F}}_{q^\ell} &&&& {\mathsf{E}}=\mathbb{F}_q[x]/(\Gamma) \\[-1mm] & \searrow && \swarrow & \\[-1mm] && \mathbb{F}_q&& \end{array}\]
As before, let \(\sigma\) be the \(q\)th-power Frobenius automorphism, and set \(\tau=\sigma^\ell\) and \(\psi=\sigma^n\). Then \(\tau\) generates \(\mathop{\mathrm{Gal}}({\mathsf{K}}/\mathsf L)\), while \(\psi\) generates \(\mathop{\mathrm{Gal}}({\mathsf{K}}/{\mathsf{E}})\). The restriction of \(\tau\) to \({\mathsf{E}}\) also generates \(\mathop{\mathrm{Gal}}({\mathsf{E}}/\mathbb{F}_q)\).
Run our normal-element algorithm over the extension \({\mathsf{K}}/\mathsf L\), which works since the base field has \(|\mathsf L|=q^\ell>n(n-1)\) elements. It returns an element \(\beta\in{\mathsf{K}}\) that is normal over \(\mathsf L\).
We use the resolvent test described in [27] for the (cyclic) extension \({\mathsf{K}}/\mathsf L\). For \(a\in{\mathsf{K}}\), define the resolvent \[\rho_\tau(a)=\sum_{i=0}^{n-1}\tau^i(a)z^i \in {\mathsf{K}}[z]/(z^n-1).\] Then \(a\) is normal over \(\mathsf L\) if and only if \(\rho_\tau(a)\) is a unit in \({\mathsf{K}}[z]/(z^n-1)\).
We extend \(\tau\) to this quotient by applying it to coefficients and fixing \(z\). In particular, the action on a resolvent \(\rho_\tau(a)\) follows a shift rule: since \(\tau\) acts on the coefficients and fixes \(z\), \[\tau(\rho_\tau(a)) = \sum_{i=0}^{n-1}\tau^{i+1}(a)z^i = z^{-1}\sum_{i=0}^{n-1}\tau^i(a)z^i = z^{-1}\rho_\tau(a),\] where the middle equality uses \(\tau^n(a)=a\) and \(z^n=1\). Let \[u=\rho_\tau(\beta)\in{\mathsf{K}}[z]/(z^n-1).\] Since \(\beta\) is normal over \(\mathsf L\), the element \(u\) is a unit. Apply \(\psi\) coefficientwise to \(u\) and multiply in the quotient ring: \[v=\prod_{j=0}^{\ell-1}\psi^j(u) \in {\mathsf{K}}[z]/(z^n-1).\] Since \(\psi\) has order \(\ell\), applying \(\psi\) cyclically permutes the factors in this product. Hence \(v\) is fixed by \(\psi\), so \(v\in{\mathsf{E}}[z]/(z^n-1)\). Moreover, \(v\) is a unit already in this smaller ring: its inverse in \({\mathsf{K}}[z]/(z^n-1)\) is also fixed by \(\psi\), hence has coefficients in \({\mathsf{E}}\). Write \(v=\sum_{i=0}^{n-1}v_i z^i\), where \(v_i\in{\mathsf{E}}\), and output \(\alpha=v_0\).
We now prove \(\alpha\) is normal over \(\mathbb{F}_q\). Since \(\tau(u)=z^{-1}u\) and \(\tau\) commutes with \(\psi\), we have \[\tau(v)=\prod_{j=0}^{\ell-1}\psi^j(\tau(u)) =\prod_{j=0}^{\ell-1}\psi^j(z^{-1}u) =z^{-\ell}v.\] Comparing coefficients gives \(\tau(v_i)=v_{i+\ell}\), with indices modulo \(n\). Since \(\alpha=v_0\), we have \(v_{r\ell}=\tau^r(\alpha)\) for all \(r\). As \(\gcd(\ell,n)=1\), the indices \(r\ell\) run through all residues modulo \(n\), and \[v=\sum_{r=0}^{n-1}\tau^r(\alpha)z^{r\ell}.\] Because \(\gcd(\ell,n)=1\), the map \(z\mapsto z^\ell\) permutes the monomials \(1,z,\ldots,z^{n-1}\) and defines an automorphism of \({\mathsf{E}}[z]/(z^n-1)\). Thus \(v\) is the image of \[\rho_\tau(\alpha)=\sum_{r=0}^{n-1}\tau^r(\alpha)z^r\] under this automorphism. Since \(v\) is a unit, so is \(\rho_\tau(\alpha)\). Applying the resolvent test to \({\mathsf{E}}/\mathbb{F}_q\) with the generator \(\tau|_{\mathsf{E}}\), we conclude that \(\alpha\) is normal over \(\mathbb{F}_q\).
The reduction is deterministic. Since \(\ell=O(\log n\log\log n)\), arithmetic in \(\mathsf L\) costs only a polylogarithmic factor over arithmetic in \(\mathbb{F}_q\). The descent computes the \(\psi\)-conjugates of \(u\) and performs \(\ell-1\) products in \({\mathsf{K}}[z]/(z^n-1)\). Using fast arithmetic in \({\mathsf{K}}\) and fast cyclic multiplication, this costs an additional \({O\,\tilde{}\,}(n^2+n\log q)\) operations over \(\mathbb{F}_q\).
The preceding construction completes the main theorem for all base-field sizes.
Theorem 5. Let \(\mathbb{F}_q\) be presented as \({\mathbb{F}}_p[y]/(\Lambda(y))\), for \(\Lambda\) irreducible in \({\mathbb{F}}_p[y]\), let \(\Gamma\) be irreducible of degree \(n\) in \(\mathbb{F}_q[{\mathcal{T}}]\) and set \({\mathsf{E}}=\mathbb{F}_q[{\mathcal{T}}]/(\Gamma({\mathcal{T}}))\). There exists a deterministic algorithm that outputs a normal element for \({\mathsf{E}}/\mathbb{F}_q\) using \[O_\epsilon((n^2 \log q)^{1+\epsilon}) + {O\,\tilde{}\,}(n\log^2 q)\] bit operations, for any fixed \(\epsilon > 0\).