Explicit computation of isomorphisms between finite fields (Q700165)

Let \(T_1\) and \(T_2\) be two irreducible polynomials of degree \(n\) over the finite field \(\mathbb F_p\), where \(p\) is a prime. Then the finite fields \(K_1 = \mathbb F_p[X]/(T_1)\) and \(K_2 = \mathbb F_p[X]/(T_2)\) both have \(p^n\) elements and so are isomorphic. The isomorphism can be represented as a polynomial \(S\) over \(\mathbb F_p\) such that \(T_1 \circ S \equiv 0 \pmod{T_2}\). The paper presents a fast algorithm to construct \(S\) using Kummer and Artin-Schreier theory. The four cases \(n \mid p-1\), \(p \nmid n\), \(n = p^k\) and \(n = qp^k\) are treated separately. When \(n \mid p-1\) there exists a primitive \(n\)th root of unity \(\zeta\) in \(\mathbb F_p\), so \(K_1\) is a Kummer extension of \(\mathbb F_p\). This simple special case of \(p \nmid n\) leads to a faster implementation. More generally, when \(p \nmid n\), let \(C = \mathbb F_p[\zeta]\). Classical Kummer theory relies on a tower of extensions of \(\mathbb F_p\), but instead the paper extends Kummer theory to the \(\mathbb F_p\)-algebra \(K_1 \otimes_{\mathbb F_p} C\) as follows. If \(k\) is a field, \(K\) a cyclic extension of \(k\) of degree \(n\) prime to the characteristic of \(k\), and \(C\) a finite extension of \(k\) containing a primitive \(n\)th root of unity, then the \(C\)-algebra \(K \otimes_k C\) is an étale algebra, i.e.\ it has no nonzero nilpotent elements. Denote by \(\sigma\) a generator of the Galois group of the extension \(K/k\). Then the set of elements of the \(k\)-algebra \(K \otimes_k C\) fixed by the automorphism \(\widetilde\sigma : x \otimes y \mapsto \sigma(x) \otimes y\) is a field isomorphic to \(C\). The characteristic polynomial of \(\sigma\) considered as an endomorphism of the \(k\)-vector space \(K\) is equal to \(X^n-1\), and ker(\(\widetilde\sigma - \zeta\text{id}\)) is a one-dimensional vector space over \(C\). If \(\alpha\) and \(\beta\) are eigenvectors of \(\widetilde\sigma\) for the eigenvalue \(1 \otimes \zeta\) then both \(\alpha^n\) and \(\beta^n\) are nonzero elements of \(k \otimes_k C\), \(\alpha^n/\beta^n\) is an \(n\)th power in \(k \otimes_k C\), and if \(\alpha^n = \beta^n\) then there exists an integer \(j\) such that \(\alpha = \widetilde\sigma^j(\beta)\). Assuming that \(\zeta\) generates \(C\) over \(k\), so that \(C = k(\zeta)\), let \(r = [C:k]\). If \(a_0\) is the first component of \(\alpha\) on the power basis \((1 \otimes \zeta^i)_{i=0}^{r-1}\) of \(K \otimes_k C\) over \(C\) then \(a_0\) is a primitive element for the extension \(K/k\). The above theory leads fairly directly to the main algorithm of the paper, in which the efficient factorization over \(\mathbb F_p\) of cyclotomic polynomials is based on Theorem 9 of \textit{V. Shoup} [J. Symb. Comput. 17, 371--391 (1994; Zbl 0815.11059)]. When \(n = p^k\), Artin-Schreier theory is used to construct almost-canonical irreducible polynomials of degree \(p^k\), using Lemma 2.3 of Shoup (loc. cit.), and an explicit algorithm is given. When \(n = qp^k\), the procedure is first to compute isomorphisms between extensions of \(\mathbb F_p\) of order \(q\) and order \(p^k\), and then combine them, following Lemma 2.4 of \textit{V. Shoup} [Math. Comput. 54, 435--447 (1990; Zbl 0712.11077)]. Finally, an algorithm is given to factorize over \(K_2\) a polynomial over \(\mathbb F_p\), based on Galois theory and using the previous algorithms to compute isomorphisms. Timings are given for an implementation using PARI [\textit{C. Batut, K. Belabas, D. Bernardi, H. Cohen,} and \textit{M. Olivier}, User's guide to PARI-GP, version 2.0.19.], which in most cases are significantly faster than the root-finding function in NTL [\textit{V. Shoup}, NTL: A library for doing number theory (version 4.0a), http://www.shoup.net/ntl/].