A Signature-Based Gröbner Basis Algorithm with Tail-Reduced Reductors (M5GB)

Gröbner bases are an important tool in computational algebra and, especially
in cryptography, often serve as a boilerplate for solving systems of polynomial
equations. Research regarding (efficient) algorithms for computing Gröbner
bases spans a large body of dedicated work that stretches over the last six
decades. The pioneering work of Bruno Buchberger in 1965 can be considered
as the blueprint for all subsequent Gröbner basis algorithms to date. Among the
most efficient algorithms in this line of work are signature-based Gr¨obner basis
algorithms, with the first of its kind published in the late 1990s by Jean-Charles
Faug`ere under the name F5. In addition to signature-based approaches, Rusydi
Makarim and Marc Stevens investigated a different direction to efficiently com-
pute Gröbner bases, which they published in 2017 with their algorithm M4GB.
The ideas behind M4GB and signature-based approaches are conceptually or-
thogonal to each other because each approach addresses a different source of
inefficiency in Buchberger’s initial algorithm by different means.
We amalgamate those orthogonal ideas and devise a new Gröbner basis
algorithm, called M5GB, that combines the concepts of both worlds. In that
capacity, M5GB merges strong signature-criteria to eliminate redundant S-pairs
with concepts for fast polynomial reductions borrowed from M4GB. We provide
proofs of termination and correctness and a proof-of-concept implementation in
C++ by means of the Mathic library. The comparison with a state-of-the-art
signature-based Gröbner basis algorithm (implemented via the same library)
validates our expectations of an overall faster runtime for quadratic overdefined
polynomial systems that have been used in comparisons before in the literature
and are also part of cryptanalytic challenges