Construction

• Construction of fields $\mbox{\rm GF}(p)$, p large; $\mbox{\rm GF}(p^n)$, p small and n large
• Optimized representations of $\mbox{\rm GF}(p^n)$ in the case of small p and large n
• Database of sparse irreducible polynomials over $\mbox{\rm GF}(2)$ for all degrees up to 11000.
• Special optimized packed arithmetic for fields of characteristic 2.
• Construction of towers of extensions
• Construction of subfields
• Compatible embedding of subfields
• Enumeration of irreducible polynomials

The finite field module uses different representations of finite field elements depending upon the size of the field. Thus, in the case of small to medium sized fields, the Zech logarithm representation is used. For fields of characteristic 2, a packed representation is used (since V2.4), which is very much faster than the representation used in previous versions of Magma. For a large degree extension K of a (small) prime field, K is represented as an extension of an intermediate field F whenever possible. The intermediate field F is chosen to be small enough so that the fast Zech logarithm representation may be used. Thus, Magma supports finite fields ranging from $\mbox{\rm GF}(2^n)$, where the degree n may be a ten thousand or more, to fields $\mbox{\rm GF}(p)$, where the characteristic p may be a thousand-bit integer. The finite field code is highly optimized for very small finite fields and especially for linear algebra over such fields.

A noteworthy feature of the facility is that no matter how a field is created, its embedding into an overfield may be determined. One may create and work within a lattice of subfields with create ease. The system is described in detail in a paper [3].