Solving a Multivariable Congruence by Change of Term Order

AbstractWe consider the congruencea≡∑i=1sbihimodIwhereh1,…,hsare given modulo a zero dimensional idealI. We give two polynomial time algorithms for determining a Gröbner basis, relative to an arbitrary term order, of the moduleMof solutions of the congruence, and, in particular, for finding its minimal element. These are based on a generalization of an algorithm of Faugéreet al. and extend the 1-variable solution techniques that use the Euclidean algorithm and the Berlekamp–Massey algorithm