Lattices of compatibly embedded finite fields (Q1369796)

The paper under review discusses the main problems involved in developing a finite field module for a computer algebra system, and describes the solutions to these problems that have been adopted in the MAGMA [\textit{J. Cannon} and \textit{C. Playoust}, Magma: A new computer algebra system, Euromath Bull. 2, 113-144 (1996)] system. Perhaps the most difficult problem is one of compatibility. Suppose \(E\) and \(F\) are finite fields with \(E\) ``contained in'' \(F\) in the sense that \(F\) contains a subfield isomorphic to \(E\). If \(S\) is another finite field explicitly embedded in both \(E\) and \(F\), then it is highly desirably to choose an explicit embedding of \(E\) in \(F\) such that, when an element of \(S\) is expressed as an element of \(F\), it does not matter whether this is done directly or via the intermediate field \(E\). Moreover, it is crucial that this compatibility be maintained as new fields are added to the lattice. Of course, in many applications one wants the possibility of having several fields of the same cardinality. The MAGMA system solves this compatibility problem in a way that involves only elementary linear algebra and the computation of roots of polynomials. In particular, an explicit representation for an embedding of \(E\) in \(F\) is stored as a matrix with entries from the common prime field \(\mathbb{Z}_p\). In terms of representing a finite field itself, MAGMA uses three basic data structures. Prime fields are of course represented by the integers modulo \(p\) with the actual implementation varying with the size of \(p\). Extension fields with cardinality at most \(2^{20}\) are represented as powers of a primitive element together with a table of logarithms used for addition, the so-called Zech representation. Larger extension fields are viewed as an extension of a Zech field, if possible, with elements represented as specialized polynomials over the Zech field. There is one misstatement in the paper noticed by the reviewer. The sequence of MAGMA commands \(F: = \text{Finite Field}(3,4)\); \(E:= \text{ext}\langle F\mid 3\rangle\); \(S:= \text{sub} \langle F \mid 2\rangle\); is supposed to construct fields with cardinalities \(3^4, 3^{12}\), and \(3^6\), respectively. In fact, the cardinality of the field \(S\) constructed will be \(3^2\). This is an annoying feature of MAGMA that does not allow the user to easily define a subfield of a specified index, but rather forces the user to specify the degree of the extension over the prime field.