An Efficient Algorithm for Computing Grobner Bases of Zero-Dimensional Ideals

摘要

This paper introduces a new efficient algorithm, called MXL_3, for computing Grobner bases of zero-dimensional ideals. The MXL_3 is based on XL algorithm, mutant strategy, and a new sufficient condition for a set of polynomials to be a Grobner basis. We present experimental results comparing the behavior of MXL_3 to F_4 on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL3 algorithm succeeds faster and uses less memory than Magma's implementation of F_4.