### A new algorithm for computing Groebner bases

Shuhong Gao, 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ère 1999), XL (Courtois et al. 2000) and F5 (Faugè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.

Note: Revised May 22, 2011.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptoanalysis
Contact author(s)
sgao @ clemson edu
History
2011-08-30: revised
See all versions
Short URL
https://ia.cr/2010/641

CC BY

BibTeX

@misc{cryptoeprint:2010/641,
author = {Shuhong Gao and Frank Volny IV and Mingsheng Wang},
title = {A new algorithm for computing Groebner bases},
howpublished = {Cryptology ePrint Archive, Paper 2010/641},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/641}},
url = {https://eprint.iacr.org/2010/641}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.