New algorithms for computing groebner bases
Shuhong Gao, Frank Volny · IACR Cryptology ePrint Archive · 2011
In this thesis, we present new algorithms for computing Grobner bases. The first algorithm, G2V, is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Grobner basis G for an ideal I and any polynomial g, and it is desired to compute a Grobner basis for the new ideal 〈 I, g〉, obtained from I by joining g. Let (I : g) denote the colon ideal of I divided by g. Our algorithm computes Grobner bases for 〈I, g〉 and (I : g) simultaneously. In previous algorithms, S-polynomials that reduce to zero are useless, in fact, F5 tries to avoid such reductions as much as possible. In our algorithm, however, these “useless” S-polynomials give elements in (I : g) and are useful in speeding up the subsequent computations. Computer experiments on some benchmark examples indicate that our algorithm is much more efficient (two to ten times faster) than F5 and F5C. Next, we present a more general algorithm that matches Buchberger's algorithm in simplicity and yet is more flexible than G2V. Given a list of polynomials, the new algorithm computes simultaneously a Grobner basis for the ideal generated by the polynomials and a Grobner basis for the leading terms of the syzygy module of the polynomials. For any term order for the ideal, one may vary the term order for the syzygy module. Under one term order for the syzygy module, the new algorithm specializes to the G2V algorithm, and under another term order for the syzygy module, the new algorithm may be several times faster than G2V, as indicated by computer experiments on benchmark examples. Finally, we present a solid theoretical framework for G2V and GVW which makes the algorithm much more understandable. This theory also gives a major improvement of the GVW algorithm. A proof of termination is provided for all algorithms, and an argument is made that GVW computes the fewest number of generators for the signature based algorithms used by GVW and F5 (similarly for G2V and F5C).