Explicit computation of isomorphisms between finite fields
type: Item
instance of: scholarly article
title: Explicit computation of isomorphisms between finite fields
zbMATH Open document ID: 1058.11071
author: Bill Allombert
published in: Finite Fields and their Applications
publication date: 2002-09-30T00:00:00Z
review text: 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…
reviewed by: Francis Wright
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11T30
zbMATH DE Number: 1809732
describes a project that uses: NTL
describes a project that uses: PARI/GP
MaRDI profile type: Publication
full work available at URL: ffta.2001.0344
OpenAlex ID: W2095191510
cites work: Q3139838
cites work: Finding Isomorphisms Between Finite Fields
cites work: Subquadratic-time factoring of polynomials over finite fields
cites work: Fast construction of irreducible polynomials over finite fields
cites work: New Algorithms for Finding Irreducible Polynomials Over Finite Fields
DOI: 10.1006/FFTA.2001.0344
description: scientific article; zbMATH DE number 1809732