skip to main content
10.1145/1390768.1390784acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

A pommaret division algorithm for computing Grobner bases in boolean rings

Published:20 July 2008Publication History

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 F2[x1,...,xn],<x12+x1,...,xn2+xn>. 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.Google ScholarGoogle ScholarCross RefCross Ref
  2. J.-C.Faugere. A new efficient algorithm for computing Grobner bases without reduction to zero (F5). Proceedings of ISSAC 2002, ACM Press, New York, 2002, pp.75--83. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. http://magma.maths.usyd.edu.au/users/allan/gb/Google ScholarGoogle Scholar
  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.Google ScholarGoogle ScholarCross RefCross Ref
  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/Google ScholarGoogle Scholar
  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.1177Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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/0408129Google ScholarGoogle Scholar
  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.Google ScholarGoogle Scholar
  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.Google ScholarGoogle Scholar
  11. Q.-N.Tran and M.Y.Vardi. Grobner Bases Computation in Boolean Rings for Symbolic Model Checking. Modelling and Simulation, R.Wamkeue (ed.), ACTA Press, 2007, pp.440--445. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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/9912029Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  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/0501111Google ScholarGoogle Scholar
  15. J.Apel. A Grobner Approach to Involutive Bases. Journal of Symbolic Computation, 19(5): 441--458, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar
  17. T.Becker, V.Weispfenning and H.Kredel. Gr\"{o}bner Bases. A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics 141, Springer-Verlag, New York, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. K.Engel. Sperner Theory. Encyclopedia of Mathematics and its Applications 65, Cambridge University Press, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. J.Apel and R.Hemmecke. Detecting unnecessary reductions in an involutive basis computation. Journal of Symbolic Computation, 40(4-5): 1131--1149, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.deGoogle ScholarGoogle Scholar
  21. http://fgbrs.lip6.fr/salsa/Software/Google ScholarGoogle Scholar
  22. http://www-sop.inria.fr/saga/POL http://www.math.uic.edu/,jan/demo.htmlGoogle ScholarGoogle Scholar
  23. V.V.Kornyak. On Compatibility of Discrete Relations. LNCS 3718, Springer-Verlag, 2005, pp.272--284. arXiv:math-ph/0504048 Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. http://invo.jinr.ruGoogle ScholarGoogle Scholar
  25. A.Semenov. On Connection Between Constructive Involutive Divisions and Monomial Orderings. LNCS 4194, Springer-Verlag, 2006, pp.261--278. Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.Google ScholarGoogle Scholar

Index Terms

  1. A pommaret division algorithm for computing Grobner bases in boolean rings

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation
      July 2008
      348 pages
      ISBN:9781595939043
      DOI:10.1145/1390768

      Copyright © 2008 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 20 July 2008

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate395of838submissions,47%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader