Solving systems of polynomial equations over Galois--Eisenstein rings with the use of the canonical generating systems of polynomial ideals

D. A. Mikhailov ; A. A. Nechaev

Diskretnaya Matematika, Tome 16 (2004) no. 1, pp. 21-51

Résumé

A Galois–Eisenstein ring or a GE-ring is a finite commutative chain ring. We consider two methods of enumeration of all solutions of some system of polynomial equations over a GE-ring $R$. The first method is the general method of coordinate-wise linearisation. This method reduces to solving the initial polynomial system over the quotient field $\bar R=R/\operatorname{Rad}R$ and then to solving a series of linear equations systems over the same field. For an arbitrary ideal of the ring $R[x_1,\ldots,x_k]$ a standard base called the canonical generating system (CGS) is constructed. The second method consists of finding a CGS of the ideal generated by the polynomials forming the left-hand side of the initial system of equations and solving instead of the initial system the system with polynomials of the CGS in the left-hand side. For systems of such type a modification of the coordinate-wise linearisation method is presented. The research was supported by the Russian Foundation for Basic Research, grants 02–01–00218, 02–01–00687, and by the President of the Russian Federation program for support of leading scientific schools, grants 2358.2003.9, 1910.2003.1.