Grobner bases over Galois rings with an application to decoding alternant codes

We develop a theory of Grobner bases over Galois rings, following the usual formulation for Grobner bases over finite fields. Our treatment includes a division algorithm, a characterization of Grobner bases, and an extension of Buchberger's algorithm. One application is towards the problem of decodi ng alternant codes over Galois rings. To this end we consider the module M = {(a, b) : aS = b mod x(r)} of all solutions to the so-called key equation for alternant codes, where S is a syndrome polynomial. In decoding, a part icular solution (Sigma, Omega) is an element of M is sought satisfying cert ain conditions, and such a solution can be found in a Grobner basis of M. A pplying techniques introduced in the first part of this paper, we give an a lgorithm which returns the required solution. (C) 2001 Academic Press.