Applying IsRewritten criterion on Buchberger algorithm

Faugère’s F5 algorithm is one of the fastest algorithms to compute Gröbner bases. It uses two criteria namely the F5 criterion and the IsRewritten criterion to detect the useless critical pairs (see Faugère (2002) [8]). The IsRewritten criterion has been used in the F5 algorithm, but it has not been explicitly declared in the related paper. In this paper, we give first a complete proof for the IsRewritten criterion and then using a signature structure on Buchberger’s algorithm, we apply this criterion on Buchberger’s algorithm. We have implemented a new algorithm (based on the above results) in Maple to compute a Gröbner basis of a general ideal and we evaluate its performance via some examples.