Cryptology ePrint Archive: Report 2010/641

A new algorithm for computing Groebner bases

Shuhong Gao and Frank Volny IV and Mingsheng Wang

Abstract: Buchberger's algorithm for computing Groebner bases was introduced in 1965, and subsequently there have been extensive efforts in improving its efficiency. Major algorithms include F4 (Faug\`{e}re 1999), XL (Courtois et al. 2000) and F5 (Faug\`{e}re 2002). F5 is believed to be the fastest algorithm known in the literature. Most recently, Gao, Guan and Volny (2010) introduced an incremental algorithm (G2V) that is simpler and several times faster than F5. In this paper, a new algorithm is presented that can avoid the incremental nature of F5 and G2V. It matches Buchberger's algorithm in simplicity and yet is more flexible. More precisely, given a list of polynomials, the new algorithm computes simultaneously a Groebner basis for the ideal generated by the polynomials and a Groebner basis for the leading terms of the syzygy module of the given list of polynomials. For any term order for the ideal, one may vary signature orders (i.e. the term orders for the syzygy module). Under one signature order, the new algorithm specializes to the G2V, and under another signature order, the new algorithm is several times faster than G2V, as indicated by computer experiments on benchmark examples.

Category / Keywords: foundations / cryptoanalysis

Date: received 15 Dec 2010, last revised 30 Aug 2011

Contact author: sgao at clemson edu

Available format(s): PDF | BibTeX Citation

Note: Revised May 22, 2011.

Version: 20110830:201033 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]