List decoding of Reed–Solomon codes from a Gröbner basis perspective

The interpolation step of Guruswami and Sudan’s list decoding of Reed–Solomon codes poses the problem of finding the minimal polynomial of an ideal with respect to a certain monomial order. An efficient algorithm that solves the problem is presented based on the theory of Gröbner bases of modules. In a special case, this algorithm reduces to a simple Berlekamp–Massey-like decoding algorithm.