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.

Bibliographie

[1] L. A. Bokut, Yu. Fong, V.-F. Ke, P. S. Kolesnikov, “Bazisy Grebnera i Grebnera–Shirshova v algebre i konformnye algebry”, Fundamentalnaya i prikladnaya matematika, 6:3 (2000), 669–706 | MR | Zbl

[2] B. Bukhberger, Dzh. Kollinz, R. Loos, Kompyuternaya algebra, Mir, Moskva, 1986 | MR

[3] A. A. Bukhshtab, Teoriya chisel, Prosveschenie, Moskva, 1966 | Zbl

[4] I. M. Vinogradov, Osnovy teorii chisel, Fizmatlit, Moskva, 1965 | MR | Zbl

[5] B. L. Van der Varden, Algebra, Nauka, Moskva, 1976 | MR

[6] M. M. Glukhov, V. P. Elizarov, A. A. Nechaev, Algebra, ch. I, Gelios, Moskva, 2003

[7] A. A. Zolotykh, A. A. Mikhalev, “Standartnye bazisy dvustoronnikh idealov svobodnykh assotsiativnykh algebr nad koltsami mnogochlenov”, Trudy pyatykh matem. chtenii MGSU, Moskva, 1997, 100–104

[8] Zolotykh A. A., Mikhalev A. A., “Algoritmy postroeniya standartnykh bazisov Grebnera–Shirshova idealov svobodnykh algebr nad kommutativnymi koltsami”, Programmirovanie, 6 (1998), 10–11 | MR | Zbl

[9] N. K. Iyudu, “Simplifikatornye svoistva slabo redutsiruemykh algebr”, Fundamentalnaya i prikladnaya matematika, 2:1 (1996), 133–146 | MR | Zbl

[10] D. Koks, Dzh. Littl, D. O'Shi, Idealy, mnogoobraziya i algoritmy: vvedenie v vychislitelnye aspekty algebraicheskoi geometrii i kommutativnoi algebry, Mir, Moskva, 2000

[11] V. N. Latyshev, Kombinatornaya teoriya kolets, standartnye bazisy, izd-vo MGU, Moskva, 1988 | MR | Zbl

[12] S. Leng, Algebra, Mir, Moskva, 1968 | MR

[13] D. A. Mikhailov, A. A. Nechaev, “Kanonicheskaya sistema obrazuyuschikh unitarnogo polinomialnogo ideala nad kommutativnym artinovym tsepnym koltsom”, Diskretnaya matematika, 13:4 (2001), 3–42 | MR | Zbl

[14] A. A. Nechaev, “O stroenii konechnykh kolets”, Matem. zametki, 10:6 (1971), 679–688 | Zbl

[15] A. A. Nechaev, “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskretnaya matematika, 3:4 (1991), 105–127 | MR | Zbl

[16] A. A. Nechaev, D. A. Mikhailov, “Ispolzovanie KSO dlya resheniya sistem uravnenii nad koltsami”, Problemy obespecheniya effektivnosti i ustoichivosti funktsionirovaniya slozhnykh tekhnicheskikh sistem, t. 2 (XXII Mezhvedomstv. nauchno-tekhn. konf.), SVI RV, Serpukhov, 2003, 49–52

[17] E. V. Pankratev, “O nekotorykh podkhodakh k postroeniyu teorii differentsialnykh bazisov Grebnera”, Matematicheskie metody i prilozheniya, izd-vo MGSU, Moskva, 2002, 132–135

[18] D. I. Pointkovskii, “Bazisy Grebnera i kogerentnost monomialnoi assotsiativnoi algebry”, Fundamentalnaya i prikladnaya matematika, 2:2 (1996), 501–509 | MR

[19] V. N. Sachkov, Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1982 | MR | Zbl

[20] A. I. Shirshov, “Nekotorye algoritmicheskie problemy dlya algebr Li”, Sib. matem. zhurnal, 3 (1962), 292–296 | Zbl

[21] J. Apel, W. Lassner, “An extension of Buchberger's algorithm and calculations in enveloping fields of Lie algebras”, J. Symbolic Comput., 6 (1988), 361–370 | DOI | MR | Zbl

[22] J. Apel, “A Gröbner approach to involutive bases”, J. Symbolic Comput., 11 (1996), 1–16 | MR

[23] J. Apel, “Computational ideal theory in finitely generated extension rings”, Theor. Computer Sci., 244 (2000), 1–33 | DOI | MR | Zbl

[24] A. V. Astrelin, E. V. Pankratiev, “Groebner bases and involutive bases”, Abstracts IMACS ACA 2000, St. Petersburg, 66–67

[25] L. Bachmair, H. Ganzinger, “Buchberger's algirithm: A constraint-based completion procedure”, Lect. Notes Comput. Sci., 845, 1994, 285–301 | MR

[26] L. Bachmair A. Tiwari, “$D$-bases for polynomial ideals over commutative noetherian rings”, Lect. Notes Comp. Sci., 230, 1997, 5–20 | MR

[27] A. M. Ballantyne, D. S. Lancford, “New decision algorithms for finitely presented commutative semigroups”, Comput. Math. Appl., 7 (1981), 159–165 | DOI | MR

[28] D. Bayer, M. Stillman, “A criterion for detecting $m$-regularity”, Invent. Math., 87 (1987), 1–11 | DOI | MR | Zbl

[29] Yu. A. Blinkov, A. Yu. Zharkov, “Involutive approach to investigating polynomial systems”, Math. Comput. Simulation, 42 (1996), 323–332 | DOI | MR

[30] T. Becker, V. Weispfenning, Gröbner bases: a computational approach to commutative algebra, Springer, Berlin, 1993 | MR

[31] W. Boege, R. Gebauer, H. Kredel, “Some examples for solving systems of algebraic equations by calculating Groebner bases”, J. Symbolic Comput., 5 (1986), 83–98 | DOI | MR

[32] B. Buchberger, An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal, Ph. D. Thesis, Univ. Innsbruck, 1965

[33] B. Buchberger, “A note on the complexity of constructing Groebner bases”, Lect. Notes Comput. Sci., 162, 1983, 137–145 | MR | Zbl

[34] B. Buchberger, “Groebner bases: An algorithmic method in polynomial ideal theory”, Recent Trends in Multidimensional System Theory, Reidel, Dordrecht, 1985, 184–232 | Zbl

[35] B. Buchberger, “A critical-pair completion algorithm for finitely generated ideals in rings”, Lect. Notes Comp. Sci., 171, 1984, 137–161 | MR | Zbl

[36] E. Byrne, P. Fitzpatrick, “Gröbner bases over Galois rings with an application to decoding alternant codes”, J. Symbolic Comput., 31 (2001), 565–584 | DOI | MR | Zbl

[37] S. Collart, M. Kalkbrener, D. Mall, “Converting Bases with the Gröbner walk”, J. Symbolic Comput., 24 (1997), 465–469 | DOI | MR | Zbl

[38] T. W. Dubé, “The structure of polynomial ideals and Gröbner bases”, SIAM J. Comput., 19 (1990), 750–775 | DOI | MR

[39] J. C. Faugère, P. Gianni, D. Lazard, T. Mora, “Efficient change of ordering for Gröbner bases of zero-dimensional ideals”, J. Symbolic Comp., 16 (1993), 329–344 | DOI | MR | Zbl

[40] J. C. Faugère, “A new efficient algorithm for computing Gröbner bases $f4$”, J. Pure and Appl. Algebra, 139 (1999), 61–88 | DOI | MR | Zbl

[41] J. C. Faugère, “A new efficient algorithm for computing Gröbner bases without reduction to zero $f5$”, ISSAC 2002, ACM Press, Paris, 2002 | MR | Zbl

[42] J. C. Faugère, J. Ars, An algebraic cryptanalysis of nonlinear filter generators using Gröbner bases, INRIA rapport, no. 4739, 2003

[43] A. Galligo, “Some algorithmic questions on ideals of differential operators”, Lect. Notes Comput. Sci., 204, 1985, 413–421 | MR | Zbl

[44] R. Gebauer, H. M. Möller, “On an installation of Buchberger's algorithm”, Computational Aspects of Commutative Algebra, Academic Press, New York, 1988, 141–152 | MR

[45] P. Gianni, T. Mora, Algebraic solution of systems of polynomial equations using Groebner bases, Lect. Notes Comput. Sci., 356, 1989 | MR | Zbl

[46] A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Taverso, ““One sugar cube, please,” or selection strategies in the Buchberger's algorithm”, ISSAC 1991, ACM Press, New York, 1991, 49–54 | Zbl

[47] D. Hartley, P. Tuckey, “Gröbner bases in Clifford and Grassman algebras”, J. Symbolic Comp., 18 (1995), 197–205 | DOI | MR

[48] D. Hilbert, “Über die Theorie der algebraischen Formen”, Math. Ann., 36 (1890), 473–534 | DOI | MR

[49] H. Hironaka, “Resolution of singularities of an algebraic variety over a field of characteristic zero, I, II”, Ann. Math., 79 (1964), 109–326 | DOI | MR | Zbl

[50] Kalkbrener M., Solving systems of algebraic equations by using Gröbner bases, Lect. Notes Comput. Sci., 378, 1987

[51] Kandri-Rody A., Kapur D., “Computing a Gröbner basis of a polynomial ideal over a Euclidean domain”, J. Symbolic Comput., 6 (1988), 37–57 | DOI | MR | Zbl

[52] Kandri-Rody A., Weispfenning V., “Non-commutative Gröbner bases in algebras of solvable type”, J. Symbolic Comput., 9 (1990), 1–26 | DOI | MR | Zbl

[53] Koblitz N., Algebraic aspects of cryptography, Springer, Berlin, 1997 | MR

[54] Kobayashi H., Moritsugu S., Hogan R. W., Solving systems of algebraic equations, Lect. Notes Comput. Sci., 358, 1989 | MR

[55] Kronecker L., Vorlesungen uber Zahlentheorie, Bd. 1, Teubner, Leipzig, 1901

[56] Krull W., “Algebraische Theorie der Ringe. II”, Math. Ann., 91 (1923), 1–46 | DOI | MR

[57] Kurakin V. L., Kuzmin A. S., Mikhalev A. V., Nechaev A. A., “Linear recurring sequences over rings and modules”, J. Math. Sci., 76:6 (1995), 2793–2915 | DOI | MR | Zbl

[58] Landau S., “Polynomial time algorithms for Galois groups”, Lect. Notes Comput. Sci., 174, 1984, 225–236 | MR | Zbl

[59] Latyshev V. N., “An improved version of standard bases”, Proc. 12th Int. Conf. Formal Power Series Algebra Comb., MSU, 2000 | MR

[60] Lazard D., “Resolution des systemes d'equations algebriques”, Teor. Comp. Sci., 15 (1981), 77–110 | DOI | MR | Zbl

[61] Lazard D., “Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations”, Lect. Notes Comput. Sci., 162, 1983, 146–156 | MR | Zbl

[62] Miller J. L., “Analogs of Gröbner bases in polynomial rings over a ring”, J. Symbolic Comp., 21 (1996), 139–153 | DOI | MR | Zbl

[63] Möller H. M., Mora F., “Upper and lower bounds for the degree of Gröbner bases”, Lect. Notes Comput. Sci., 174, 1984, 172–183 | MR | Zbl

[64] Mora T., Seven variations on standard bases, Preprint, Univ. di Genova, Dip. di Mathematica, 1988

[65] Norton G. H., Salagean A., “Strong Gröbner bases and cyclic codes over a finite-chain ring”, Proc. Int. Workshop on Coding and Cryptography, Paris, 2001, 391–401 | MR

[66] Pan L., “On the $D$-bases of polynomial ideals over principal ideal domains”, J. Symbolic Comput., 7 (1988), 55–69 | DOI | MR

[67] Robbiano L., “Term orderings on the polynomial ring”, Lect. Notes Comput. Sci., 204, 1985, 513–517 | MR | Zbl

[68] Robbiano L., “On the theory of graded structures”, J. Symbolic Comp., 5 (1986), 139–170 | DOI | MR

[69] Stifter S., “A generalization of reduction rings”, J. Symbolic Comput., 6 (1987), 351–364 | DOI | MR

[70] Trinks W. L., “Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen”, J. Number Theory, 10 (1978), 475–488 | DOI | MR | Zbl

[71] Winkler F., “On the complexity of the Gröbner bases algorithm over $K[x,y,z]$”, Lect. Notes Comput. Sci., 174, 1984, 184–194 | MR | Zbl

[72] Zacharias G., Generalized Gröbner bases in commutative polynomial rings, Bachelor Thesis, MIT, Boston, 1978