Faugère's F4 and F5 algorithms

In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate polynomial ring. The algorithm uses the same mathematical principles as the Buchberger algorithm, but computes many normal forms in one go by forming a generally sparse matrix and using fast linear algebra to do the reductions in parallel.

The Faugère F5 algorithm first calculates the Gröbner basis of a pair of generator polynomials of the ideal. Then it uses this basis to reduce the size of the initial matrices of generators for the next larger basis:

If G_prev is an already computed Gröbner basis (f₂, …, f_m) and we want to compute a Gröbner basis of (f₁) + G_prev then we will construct matrices whose rows are m f₁ such that m is a monomial not divisible by the leading term of an element of G_prev.

This strategy allows the algorithm to apply two new criteria based on what Faugère calls signatures of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called regular sequences, without ever simplifying a single polynomial to zero—the most time-consuming operation in algorithms that compute Gröbner bases. It is also very effective for a large number of non-regular sequences.

Implementations

The Faugère F4 algorithm is implemented

• as a package FGb for the Maple computer algebra system. This package is included in Maple distribution as the option method=fgb of function Groebner[gbasis];
• in the Magma computer algebra system.
• as a C library.

Study versions of the Faugère F5 algorithm is implemented in

• the SINGULAR computer algebra system;
• the Sage computer algebra system.

Applications

The previously intractable "cyclic 10" problem was solved by F5, as were a number of systems related to cryptography; for example HFE and C^*.

References

• Till Stegers Faugere's F5 Algorithm Revisited (alternative link). Diplom-Mathematiker Thesis, advisor Johannes Buchmann, Technische Universität Darmstadt, September 2005 (revised April 27, 2007). Many references, including links to available implementations.

External links

• Faugère's home page (includes pdf reprints of additional papers)
• An introduction to the F4 algorithm.