Efficient Gröbner bases computation over principal ideal rings

Abstract In this paper we present new techniques for improving the computation of strong Grobner bases over a principal ideal ring R . More precisely, we describe how to lift a strong Grobner basis along a canonical projection R → R / n , n ≠ 0 , and along a ring isomorphism R → R 1 × R 2 . We then apply this to the computation of strong Grobner bases over a non-trivial quotient of a principal ideal domain R / n R . The idea is to run a standard Grobner basis algorithm pretending R / n R to be field. If we discover a non-invertible leading coefficient c, we use this information to try to split n = a b with coprime a , b . If this is possible, we recursively reduce the original computation to two strong Grobner bases computations over R / a R and R / b R respectively. If no such c is discovered, the returned Grobner basis is already a strong Grobner basis for the input ideal over R / n R .