Finite Fields

Introduction

A large amount of effort has been put into producing fast tools for computing with finite fields as well as with matrices and polynomials over finite fields. Thus, numerous techniques are employed to achieve fast arithmetic in very large finite fields, such as characteristic 2 fields of degree 10,000 upwards.

Linear algebra over finite fields is highly optimised, with a different scheme being used for packing the components of a GF(q)-vector used for each field of cardinality up to 8 so as to achieve fast parallel row reduction. For field cardinalities greater than 8, different vector packing schemes are employed for different ranges of possible cardinalities.

A range of methods are available for solving the discrete log problem. At present these concentrate on small characteristics but future work will provide faster methods for medium and large characteristics. A novel feature is the provision of databases containing the logarithms of factor bases for finite fields GF(pⁿ), where p is small.

In this section, K will denote the finite field GF(pⁿ), where p is a prime.

Representation and Basic Arithmetic

A variety of representations are used for finite fields in Magma, depending on the characteristic and degree. This ensures that operations are as fast as possible (not just for basic arithmetic but also for in polynomial algebra and linear algebra over finite fields) while saving memory for small fields.

For a prime field GF(p), a packed representation is used for small p and Magma's large integer package is used for large p. For an extension field K = GF(q), where q = p^d, d > 1, a variety of representations are used:

• If q ≤ 2²⁰ the Zech logarithm representation is used, where elements are stored as logarithms and addition/subtraction is done via lookup table taking O(q) space. This is typically much faster than a polynomial representation since one does not need a separate memory block for each element and the lookup table is very fast to access.
• A polynomial representation, which uses the asymptotically-fast univariate polynomial operations over the prime field GF(p); this is particularly efficient in very high degree.
• A ‘hybrid’ polynomial representation, which internally rewrites the field K over a subfield S with the Zech representation which is as large as possible. Then elements of K can be written as polynomials over S of degree lower than d so the polynomial arithmetic is faster. This representation is only applicable when d has suitable divisors and depends heavily on an automatic compatibility scheme (see below) to manage the mappings between the different representations in the background, but all of this is automated and hidden from the user. For example, the user may have K = GF(2³) and define L as a degree-8 extension of K with a certain polynomial; now L will be internally represented as a suitable degree-3 extension of S = GF(2⁸) where S has the Zech representation; this makes the arithmetic much faster, but L and its elements will still be explicitly presented to the user as an extension of K.
• A special packed representation is used in both characteristic 2 and 3 (when q is out of the Zech logarithm range). In characteristic 2, this also includes the use of special machine instructions for multiplication on recent Intel and AMD processors. For example, in GF(2¹⁰⁰⁰⁴³) one thousand element products can be computed in about 0.6 seconds.

Magma also has special code for fast evaluation of the Frobenius map based on linear algebra and this is exploited in several contexts. Apart from the basic arithmetic operations, there is a sophisticated algorithm to compute kth roots of elements of fields, where k may be an arbitrary positive integer.

Compatibility and Subfield Embeddings

The most critical feature which is unique to Magma's finite field machinery is automatic guarantee of compatibility; that is, one can construct an arbitrary lattice of finite fields of characteristic p by successively creating extension fields (via any irreducible polynomials) and subfields in any order and it is guaranteed that the diagram of subfields commutes (that is, when mapping an element through various relationships between subfields the result is the same no matter which path is taken).

The theoretical scheme which ensures this compatibility condition was developed by A. Steel in 1993 and strongly depends on linear algebra for managing the variety of background mappings. The scheme does not depend in any way on Conway polynomials (by which a lattice of subfields is defined only by direct extensions of the prime field using a fixed set of irreducible polynomials from a database). The Magma mechanism allows the user to create arbitrary chains of extensions (with arbitrary irreducible polynomials defining the extensions) and embed fields into each other when applicable; also, field elements can be embedded in any subfield and allow related operations, such as computing the minimal polynomial of an element with respect to any given subfield.

Discrete Logarithms

Magma provides machinery for computing discrete logarithms in any supported finite field no matter which field representation is used. Suppose w is a chosen primitive element of K. The discrete logarithm problem (DLP) for K is, given arbitrary non-zero element x of K, find an integer e such that x = w^e. Let m = q – 1 be the order of the multiplication group G of K. The Pohlig–Hellman algorithm reduces the problem to computing e modulo each prime power factor of m. Methods such as the Pollard rho algorithm with square root complexity can do this quite quickly provided that the cardinality l of the largest Sylow p-subgroup of G is less than 10¹⁵.

If l is too large for the Pollard rho algorithm, then the index calculus method is used. This method has subexponential complexity. Magma has a number of implementations of the index calculus algorithm which are capable of solving the DLP in fields having small characteristics and cardinalities up to 10¹⁸⁰, at least. In 2012, a database was developed by A. Steel which contains the logarithms of a factor base for many finite fields having small characteristics thereby avoiding a precomputation step that potentially could take a very long time. The complete database currently includes logarithms at least for the fields GF(p^d) for:

• p = 2: all d ≤ 450 and all prime d up to 503;
• p = 3: all d ≤ 270 (427 bits);
• p = 5: all d ≤ 219 (509 bits);
• p = 7: all d ≤ 150 (421 bits);
• p = 11: all d ≤ 85 (294 bits);
• p = 13: all d ≤ 72 (266 bits);
• 13 < p < 97: several non-trivial fields.