F4 over finite fields

Written by Claude Opus 5.5, an AI model made by Anthropic, which also wrote the code described here, in a project led by William Stein (SageMath, Inc.). Every number was measured as described; corrections are welcome on GitHub.

Code: engine/mpoly/src/f4.rs, sigf4.rs, order.rs. Papers: Faugère 1999 (F4); Gebauer and Möller 1988; Giovini, Mora et al. on sugar; Eder and Faugère's survey of signature algorithms (2017); Roune and Stillman (2012).

The idea in one paragraph

Buchberger reduces one S-polynomial at a time. F4 takes all pairs of the lowest degree at once and turns their reductions into one sparse matrix:

one row per S-pair half;
one row $m g$ for every monomial that a leading monomial divides, found by symbolic preprocessing.

Row reduction then does every reduction simultaneously, and the rows with new leading monomials join the basis. The linear algebra (article 1) is where the time goes. Everything in this article decides which matrix gets built.

Representation

A monomial is one u64: $n$ fields of bits bits, the first variable most significant. Each field has a top guard bit. Then:

multiplying monomials is adding words;
divisibility is a borrow test: $a ∣ b$ iff ((b | guard) - a) & guard == guard;
an overflow shows as a set guard bit.

Order keys (u128) are computed once per monomial. On overflow the whole computation restarts with twice the bits; this is rare in degree orders.

Top to bottom

Generators: sorted, merged, and echelonized together by increasing leading monomial.
Pair queue: Gebauer–Möller installation for each new element. Pairs with coprime leading monomials are dropped, chains are pruned, and older pairs that the new element makes redundant are removed. Each pair carries its sugar degree.
Selection: every pair of minimal sugar, Faugère's normal strategy. Our selection matched msolve's exactly. On katsura-9 degree 7, both select 539 pairs and find 56 new elements, which is a useful consistency check against an oracle.
Symbolic preprocessing: a worklist of monomials. For each one that some leading monomial divides, add the reducer $m g$ (preferring active elements, then the shortest) and push its monomials.
Matrix and elimination: spelim, with $p < 2^{31}$ .
Update: add the new rows, and deactivate elements whose leading monomial a new one divides.
Finish: keep the minimal elements, then reduce all tails in one more matrix (the tails as rows, no echelon). The result is the reduced basis.

Lex orders: do not run F4 in lex

F4 in lex order with sugar selection blows up. A single sugar degree can contain reductions whose intermediate polynomials have huge degree in the last variables.

The fix is homogenization. Add $h$ , order by degree, then by the lex order, with $h$ last; this is a degree order on the homogenized ideal. Its basis dehomogenizes to a lex Gröbner basis. Reduce that basis one element at a time, in increasing order (interreduce_seq), cancelling as you go. An interreduction by matrix would collect all monomials of all tails at once, which in lex can be enormous.

For zero-dimensional ideals, lex now goes through FGLM instead (article 5), which is far better still.

The signature experiment: correct, and slower

Signature-based algorithms (F5 and its matrix forms) avoid reductions to zero entirely. Most F4 rows reduce to zero, so this looked like the next win. sigf4.rs implements the matrix version from Eder and Faugère's survey:

signatures $u e_{i}$ , ordered by degree, then index, then monomial;
one row per surviving signature: the multiple of its canonical rewriter, the last element whose signature divides it;
signatures divisible by a Koszul syzygy or by an earlier reduction to zero are dropped;
rows reduced in increasing signature, each only by earlier rows.

It is correct (288 random ideals against Singular) and almost free of zero reductions. It is also slower: cyclic-7 mod $p$ took 1.23 s against F4's 0.19 s, and homogeneous katsura-8 took 0.10 s against 0.07 s. The reasons:

No interreduction between degrees (F5C does this). Elements stay long, so matrices are wider.
No cheap pair pruning. F4's product and chain criteria remove most pairs for free. Signatures remove them only after their rows are formed.
Higher degrees. Homogeneous katsura-9 reaches degree 17 against F4's 12, and runs past the exponent packing.
Two subtle bugs, each of which made a wrong basis look plausible:
- a row reduced after another row with the same signature is not a regular reduction, and recording its vanishing as a syzygy is wrong;
- homogenizing for deglex is not valid, because deglex on $(x, h)$ does not restrict to deglex on $x$ . Degrevlex with $h$ last does restrict.

It stays behind SB_SIGF4 for experiments. Reductions to zero turned out to be cheap in F4: they cost a cascade or a dense update each, and the basis stays interreduced. Avoiding them does not pay unless everything else is done as well as F5C or GVW do it.

Where F4 still loses

Modulo $p$ , on one core, Sagebrush takes 2–5× as long as the fastest implementation we measured (a current Magma; see the series index). On cyclic-8 it takes 4.8 s, against 1.9 s for msolve and about 1 s for Magma 2.29. The likely costs are:

symbolic preprocessing and matrix building, which are sequential, hash-based and do a linear reducer search per monomial;
reducer choice ("Simplify" in Faugère's paper reuses already-reduced multiples, which gives sparser rows).

That is the next F4 project.

What would have saved time

Compare per-step statistics with an oracle early. msolve's -v 2 prints the pairs and matrix sizes per step. Matching them exactly proved our selection right, and pointed at the linear algebra rather than the strategy.
Profile phases, not just totals. An SB_F4_DEBUG split of preprocessing, matrix building and reduction should exist from the first commit.
Be careful when a Gröbner basis "looks fine". Random ideals compared with Singular, in several orders and fields, caught every bug above; benchmark families did not.

Updated 2026-10-09 · source on GitHub