M4GB
swMATH ID:  35027 
Software Authors:  Makarim, Rusydi H.; Stevens, Marc 
Description:  M4GB. An efficient Gröbnerbasis algorithm. This paper introduces a new efficient algorithm for computing Grobnerbases named M4GB. Like Faugere’s algorithm F4 it is an extension of Buchberger’s algorithm that describes: how to store already computed (tail)reduced multiples of basis polynomials to prevent redundant work in the reduction step; and how to exploit efficient linear algebra for the reduction step. In comparison to F4 it removes further redundant work in the processing of reducible monomials. Furthermore, instead of translating the reduction of many critical pairs into the row reduction of some large matrix, our algorithm is described more natively and is efficient while processing critical pairs one by one. This feature implies that typically M4GB has to process fewer critical pairs than F4, and reduces the time and data complexity ‘staircase’ related to the increasing degree of regularity for a sequence of problems one observes for F4. To achieve high efficiency, M4GB has been designed specifically to operate only on tailreduced polynomials, i.e., polynomials of which all terms except the leading term are nonreducible. This allows it to perform fullreduction directly in the computation of a term polynomial multiplication, where all computations are done over coefficient vectors over the nonreducible monomials. We have implemented a version of our new algorithm tailored for dense overdefined polynomial systems as a proof of concept and made our source code publicly available. We have made a comparison of our implementation against the implementations of FGBlib, Magma and OpenF4 on various dense Fukuoka MQ challenge problems that we were able to compute in reasonable time and memory. We observed that M4GB uses the least total CPU time and the least memory of all these implementations for those MQ problems, often by a significant factor. In the Fukuoka MQ challenges, the starting challenges of Type V and Type VI have 16 equations which was chosen based on an extrapolated computational runtime of more than a month using Magma. M4GB allowed us to set new records for these Fukuoka MQ challenges breaking Type V ((mathbb{F}_{2^8})) up to 18 equations and Type VI ((mathbb{F}_{31})) up to 19 equations, each can be computed within up to 11 days on our dual Xeon system. 
Homepage:  https://marcstevens.nl/research/papers/ISSAC17MSM4GB.pdf 
Source Code:  https://github.com/crmarcstevens/m4gb 
Keywords:  Gröbner basis algorithm; multivariate polynomial systems; quantumsafe public key crypto 
Related Software:  FGb; fgb_sage; Sidon Cryptosystem; ZHFE; SageMath; openf4; Magma 
Cited in:  4 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

M4GB. An efficient Gröbnerbasis algorithm. Zbl 1457.68329 Makarim, Rusydi H.; Stevens, Marc 
2017

all
top 5
Cited by 8 Authors
1  Langton, Ben 
1  Makarim, Rusydi H. 
1  Novoselov, S. A. 
1  Raviv, Netanel 
1  Stevens, Marc 
1  Stigler, Brandilyn 
1  Tamo, Itzhak (Zachi) 
1  Zhang, Anyu 
Cited in 1 Serial
1  Finite Fields and their Applications 
Cited in 5 Fields
2  Number theory (11XX) 
2  Commutative algebra (13XX) 
2  Information and communication theory, circuits (94XX) 
1  Algebraic geometry (14XX) 
1  Computer science (68XX) 