Gröbner bases

Introduction

A Gröbner basis of an ideal I = < f₁,…, f_k > of the multivariate polynomial ring R = K[x₁,…,x_n] (where K is a field or Euclidean ring) is a canonical generating set of I which yields information from which many important properties of I can be determined. For example, if G is a Gröbner basis of I, then one can easily test whether an arbitrary polynomial f∈R is in I, or one can instantly determine from G whether the underlying system of polynomial equations has a solution (and also the number of solutions over an algebraic closure when the number is finite); if G is also written with respect to a lexicographical order (see below), then one can quickly read off all solutions to the system of equations. The Gröbner basis machinery in Magma was designed and implemented by A. Steel.

The worst-case theoretical complexity for computing a Gröbner basis is doubly exponential in the maximum degree of the input polynomials; this holds for the space usage as well as the time taken. Thus, it may not be feasible to construct a Gröbner basis within the memory of any computer, even ignoring the time taken. However, there is a vast range of ideals for which computing a Gröbner basis is quite feasible. Much of Algebraic and Arithmetic Geometry depends heavily on Gröbner bases for non-trivial operations on ideals and modules of multivariate polynomial rings, but major applications occur in a huge number of disciplines.

Magma is widely recognised by workers in the field as having the broadest and fastest Gröbner Basis machinery in general for any CAS. Magma's package for Gröbner bases is doubly generic in the following sense:

• All the Gröbner basis machinery works generically for ideals defined over an arbitrary field or Euclidean ring (as is the case with Magma's linear algebra). Apart from the generic versions, highly optimised versions have been developed for working with ideals defined over specific types of field which arise frequently in practice such as small finite fields and ℚ.
• All of the Gröbner basis machinery works generically for a wide range of machine representations of monomials. These includes not only several forms of packed representations for the standard commutative monomials (including sparse and dense variants, selected according to the number of variables), but special representations such as bit-vector representations for system solving over GF(2) and for non-commutative settings, such as exterior algebras, solvable algebras, and general non-commutative algebras.

The Faugere F₄ algorithm

The traditional algorithm for computing a Gröbner basis is Buchberger's algorithm, published by Buchberger in 1965. In 1999, J.-C. Faugère introduced his so-called F₄ algorithm which is generally more efficient than the Buchberger algorithm. The F₄ algorithm basically consists of a series of steps in each of which a hash table of monomials is built up and a related matrix is constructed in parallel (with columns labelled by the hash table entries) and then the matrix is reduced by Gaussian elimination; this avoids expensive repeated operations on common monomials which dominate the computation when the Buchberger algorithm is used.

The matrices constructed in the F₄ algorithm are typically globally sparse but may be extremely large and have very dense patches (e.g., for the 80-variable HFE challenge below, the largest matrix is 293,287×1,666,981 and many rows have hundreds of thousands of non-zero entries). Traditional linear algebra algorithms are designed for either sparse matrices or for dense matrices and are not applicable to this situation, so the reduction of the matrix requires highly specialist code which works row by row with the mixture of sparse and dense rows. Thus Magma's implementation has a special representation for these kinds of matrices (only used in the F₄ algorithm) and based on this, the algorithm is highly optimised for several different types of finite fields and also includes modular algorithms for the rational field and number fields.

A major new variant of the F₄ algorithm was developed by A. Steel in 2013 and is applicable to polynomial systems with rather dense inputs; this is a common case for attacking certain types of cryptosystem and includes the HFE and MQQ cryptosystems and also Minrank systems. This variant makes Magma even faster than before for several types of polynomial systems.

All the timings given below are for runs on a 64-bit Dell workstation with a 4-core Intel Core i7-7700 CPU (3.60 GHz); timings are given for runs in both the default single core case and the parallel 4-core case.

Gröbner Bases over Finite Fields and Algebraic Attacks

The case in which the coefficient ring is a finite field is of considerable interest. For computing such Gröbner bases, Magma has a variety of optimal representations for the linear algebra phase of the F₄ algorithm. The critical case of GF(p), where p is a moderately small prime, is handled by exact floating point operations so that the primitive vector operations are highly optimised. This approach is also the basis of the characteristic zero algorithms below. For example, Magma V2.27 computes:

• The Gröbner basis of the Cyclic-9 roots ideal over GF(32003) in 10.2 secs (4 cores) or in 29.3 secs (1 core);
• The Gröbner basis of the Cyclic-10 roots ideal over GF(32003) in 601.2 secs (4 cores) or in 1957.1 secs (1 core).

Algebraic attacks on cryptosystems have become of increasing importance and basically involve solving large multivariate polynomial systems over a small finite field, particularly GF(2). Magma contains special extensions of the F₄ algorithm for solving large multivariate polynomial systems over GF(2). This includes a special bit vector representation for monomials (x² = x for each variable in this context) together with an optimal numbering scheme for monomials. (A hash table takes too much memory when there is a huge number of variables.)

For example, Magma apparently remains the only publically-available software which is able to solve Patarin's first Hidden Field Equations (HFE) Crypto Challenge. The input for this system consists of 80 quadratic polynomials in 80 variables over GF(2) and Magma V2.27 solves the challenge in 28.2 secs (4 cores) or in 85.1 secs (1 core) with the dense variant.

Gröbner Bases over Characteristic Zero Fields

Since knowledge of a Gröbner basis is a popular approach to solving systems of polynomial equations, being able to compute Gröbner bases in characteristic zero is required by a great number of applications in areas of mathematics such as commutative algebra, algebraic geometry, and arithmetic geometry. For ideals over ℚ, Magma contains a highly optimised modular algorithm for the linear algebra phase of the F₄ algorithm which can compute large Gröbner bases with large rational coefficients in reasonable time. For example, Magma V2.27 computes:

• The Gröbner basis of the Cyclic-9 roots ideal over ℚ in 144.3 secs (4 cores) or in 286.1 secs (1 core), using 750 MB for either computation;
• The Gröbner basis of the Cyclic-10 roots ideal over ℚ in 5.2 hours (4 cores) or in 16.1 hours (1 core), using 46 GB for either computation.

For computing Gröbner bases of ideals over a number field K = Q(α), Magma also contains a ‘double’ modular algorithm for the linear algebra phase of the F₄ algorithm, which works by mapping K into several finite fields and using both interpolation and Chinese Remaindering. This modular algorithm is often dramatically faster than the standard (non-modular) algorithm since it avoids the intermediate coefficient blowup which quickly arises in any non-trivial computation with number fields.