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.
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- http://magma.maths.usyd.edu.au/users/allan/gb/Google Scholar
- 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 ScholarCross Ref
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 Scholar
- J.Apel. A Grobner Approach to Involutive Bases. Journal of Symbolic Computation, 19(5): 441--458, 1995. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- K.Engel. Sperner Theory. Encyclopedia of Mathematics and its Applications 65, Cambridge University Press, 1997. Google ScholarDigital Library
- J.Apel and R.Hemmecke. Detecting unnecessary reductions in an involutive basis computation. Journal of Symbolic Computation, 40(4-5): 1131--1149, 2005. Google ScholarDigital Library
- 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 Scholar
- http://fgbrs.lip6.fr/salsa/Software/Google Scholar
- http://www-sop.inria.fr/saga/POL http://www.math.uic.edu/,jan/demo.htmlGoogle Scholar
- V.V.Kornyak. On Compatibility of Discrete Relations. LNCS 3718, Springer-Verlag, 2005, pp.272--284. arXiv:math-ph/0504048 Google ScholarDigital Library
- http://invo.jinr.ruGoogle Scholar
- A.Semenov. On Connection Between Constructive Involutive Divisions and Monomial Orderings. LNCS 4194, Springer-Verlag, 2006, pp.261--278. Google ScholarDigital Library
- 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 Scholar
Index Terms
A pommaret division algorithm for computing Grobner bases in boolean rings
Recommendations
Boolean Gröbner bases
In recent years, Boolean Grobner bases have attracted the attention of many researchers, mainly in connection with cryptography. Several sophisticated methods have been developed for the computation of Boolean Grobner bases. However, most of them only ...
Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computationIn this paper, we propose an efficient method to solve polynomial systems whose equations are left invariant by the action of a finite group G. The idea is to simultaneously compute a truncated SAGBI-Gr¨obner bases (a generalisation of Gr¨obner bases to ...
Comprehensive Gröbner bases and regular rings
Commutative von Neumann regular rings can be viewed as certain subdirect products of fields. So in some sense they can code arbitrary sets of fields. It was shown in 1987 that most of the Grobner basis theory over fields initiated by B. Buchberger can ...
Comments