A pommaret division algorithm for computing Grobner bases in boolean rings

ABSTRACT

In this paper an involutive algorithm for construction of Grobner bases in Boolean rings is presented. The algorithm exploits the Pommaret monomial division as an involutive division. In distinction to other approaches and due to special properties of Pommaret division the algorithm allows to perform the Grobner basis computation directly in a Boolean ring which can be defined as the quotient ring F₂[x₁,...,x_n],1²+x₁,...,x_n²+x_n>. Some related cardinality bounds for Pommaret and Grobner bases are derived. Efficiency of our first implementation of the algorithm is illustrated by a number of serial benchmarks.

REFERENCES

• 1: J.-C.Faugere and A.Joux. Algebraic Cryptanalysis of Hidden Field Equations (HFE) Using Grobner Bases. LNCS 2729, Springer-Verlag, 2003, pp.44--60.
• 2: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 3: http://magma.maths.usyd.edu.au/users/allan/gb/
• 4: J.-C.Faugere. A new efficient algorithm for computing Grobner bases ($F_4$). Journal of Pure and Applied Algebra, 139(1-3): 61--68, 1999.
• 5: M.Brickenstein and A.Dreyer. PolyBoRi: A framework for Grobner basis computations with Boolean polynomials. Electronic Proceedings of the MEGA 2007. http://www.ricam.oeaw.ac.at/mega2007/
• 6: M.Brickenstein, A.Dreyer, G.-M.Greuel and O.Wienand. New developments in the theory of Grobner bases and applications to formal verification. arXiv:math.AC/0801.1177
• 7: C.Condrat and P.Kalla. A Gr\"{o}bner Basis Approach to CNF-Formulae Preprocessing. Tools and Algorithms for the Construction and Analysis of Systems. LNCS 4424, Springer-Verlag, 2007, pp.618--631.
• 8: C.M.Dawson, H.L.Haselgrove, A.P.Hines, D.Mortimer, M.A.Nielsen and T.J.Osborne. Quantum computing and polynomial equations over the finite field Z2. arXiv:quant-ph/0408129
• 9: V.P.Gerdt, R.Kragler and A.N.Prokopenya. On Computer Algebra Application to Simulation of Quantum Computation. Models and Methods in Few-and Many-Body Systems, S.A.Sofianos (ed.). University of South Africa, Pretoria, 2007, pp.219--232.
• 10: M. Bardet, J.-C.Faug\`{e}re and B.Salvy. Complexity of Gr\"{o}bner Basis computation for Semi-regular Overdetermined sequences over F2 with solutions in F2. INRIA report RR-5049, 2003.
• 11: Quocnam Tran , Moshe Y. Vardi, Groebner bases computation in Boolean rings for symbolic model checking, Proceedings of the 18th conference on Proceedings of the 18th IASTED International Conference: modelling and simulation, p.440-445, May 30-June 01, 2007, Montreal, Canada
• 12: V.P.Gerdt and Yu.A.Blinkov. Involutive Bases of Polynomial Ideals. Mathematics and Computers in Simulation, 45:519--542, 1998. arXiv:math.AC/9912027; Minimal Involutive Bases. ibid., 543--560, arXiv:math.AC/9912029
• 13: V.P.Gerdt, Yu.A.Blinkov and D.A.Yanovich. Construction of Janet bases. I. Monomial bases. Computer Algebra in Scientific Computing / CASC 2001, Springer-Verlag, Berlin, 2001, pp.233--247; II. Polynomial bases, ibid., pp.249--263.
• 14: V.P.Gerdt. Involutive Algorithms for Computing Grobner Bases. Computational Commutative and Non-Commutative Algebraic Geometry, S.Cojocaru, G.Pfister and V.Ufnarovski (eds.), NATO Science Series, IOS Press, 2005, pp. 199--225. arXiv:math.AC/0501111
• 15: Joachim Apel, A Gro¨bner approach to involutive bases, Journal of Symbolic Computation, v.19 n.5, p.441-457, May 1995 [doi>10.1006/jsco.1995.1026]
• 16: B.Buchberger. Gr\"{o}bner Bases: an Algorithmic Method in Polynomial Ideal Theory. Recent Trends in Multidimensional System Theory, N.K. Bose (ed.), Reidel, Dordrecht, 1985, pp.184--232.
• 17: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 18: Konrad Engel, Sperner theory, Cambridge University Press, New York, NY, 1997
• 19: J.Apel and R.Hemmecke. Detecting unnecessary reductions in an involutive basis computation. Journal of Symbolic Computation, 40(4-5): 1131--1149, 2005.
• 20: G.-M.Greuel, G.Pfister and H.Schonemann. Singular 3.0.4. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern, 2007. http://www.singular.uni-kl.de
• 21: http://fgbrs.lip6.fr/salsa/Software/
• 22: http://www-sop.inria.fr/saga/POL http://www.math.uic.edu/,jan/demo.html
• 23: V.V.Kornyak. On Compatibility of Discrete Relations. LNCS 3718, Springer-Verlag, 2005, pp.272--284. arXiv:math-ph/0504048
• 24: http://invo.jinr.ru
• 25: A.Semenov. On Connection Between Constructive Involutive Divisions and Monomial Orderings. LNCS 4194, Springer-Verlag, 2006, pp.261--278.
• 26: W.M.Seiler. A Combinatorial Approach to Involution and Delta-Regularity I: Involutive Bases in Polynomial Algebras of Solvable Type; II: Structure Analysis of Polynomial Modules with Pommaret Bases, Preprints, Universitat Kassel, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
boolean ring, groebner basis, involutive algorithm, pommaret division