Up | Next | Prev | PrevTail | Tail |
Authors: Yuri A. Blinkov and Mikhail V. Zinin
Involutive polynomial bases are redundant Gröbner bases of special structure with some additional useful features in comparison with reduced Gröbner bases [?]. Apart from numerous applications of involutive bases [?] the involutive algorithms [?] provide an efficient method for computing reduced Gröbner bases. A reduced Gröbner basis is a well-determined subset of an involutive basis and can be easily extracted from the latter without any extra reductions. All this takes place not only in rings of commutative polynomials but also in Boolean rings.
Boolean Gröbner basis already have already revealed their value and usability in practice. The first impressive demonstration of practicability of Boolean Gröbner bases was breaking the first HFE (Hidden Fields Equations) challenge in the public key cryptography done in [?] by computing a Boolean Gröbner basis for the system of quadratic polynomials in 80 variables. Since that time the Boolean Gröbner bases application area has widen drastically and nowadays there is also a number of quite successful examples of using Gröbner bases for solving SAT problems.
During our research we had developed [?, ?, ?] Boolean involutive algorithms based on Janet and Pommaret divisions and applied them to computation of Boolean Gröbner bases. Our implementation of both divisions has experimentally demonstrated computational superiority of the Pommaret division implementation. This package BIBASIS is the result of our thorough research in the field of Boolean Gröbner bases. BIBASIS implements the involutive algorithm based on Pommaret division in a multivariate Boolean ring.
In section 2 the Boolean ring and its peculiarities are shortly introduced. In section 3 we briefly argue why the involutive algorithm and Pommaret division are good for Boolean ring while the Buhberger’s algorithm is not. And finally in section 4 we give the full description of BIBASIS package capabilities and illustrate it by examples.
Boolean ring perfectly goes with its name, it is a ring of Boolean functions of n variables, i.e mappings from {0,1}n to {0,1}n. Considering these variables are X := {x1,…,xn} and F2 is the finite field of two elements {0,1}, Boolean ring can be regarded as the quotient ring
Detailed description of involutive algorithm can found in [?]. Here we note that result of both involutive and Buhberger’s algorithms depend on chosen monomial ordering. At that the ordering must be admissible, i.e.
The involutive algorithm based on Janet division has the same disadvantage unlike the Pommaret division algorithm as shown in [?]. The Pommaret division algorithm can be applied directly in a Boolean ring and admits effective data structures for monomial representation.
The package BIBASIS implements the Pommaret division algorithm in a Boolean ring. The first step to using the package is to load it:
The current version of the BIBASIS user interface consists only of 2 functions: bibasis and bibasis_print_statistics.
The bibasis is the function that performs all the computation and has the following syntax:
bibasis(initial_polynomial_list, variables_list, monomial_ordering, reduce_to_groebner);
Input:
See Examples 2—4 to check that Gröbner (as well as involutive) basis depends on monomial ordering.
Output:
The syntax of bibasis_print_statistics is simple:
bibasis_print_statistics();
This function prints out a brief statistics for the last invocation of bibasis function. See Example 7.
Example 1:
Example 2:
Example 3:
Example 4:
Example 5:
Example 6:
Example 7:
[1] V.P.Gerdt and Yu.A.Blinkov. Involutive Bases of Polynomial Ideals. Mathematics and Computers in Simulation, 45, 519–542, 1998; Minimal Involutive Bases, ibid. 543–560.
[2] W.M.Seiler. Involution: The Formal Theory of Differential Equations and its Applications in Computer Algebra. Algorithms and Computation in Mathematics, 24, Springer, 2010. arXiv:math.AC/0501111
[3] Vladimir P. Gerdt. Involutive Algorithms for Computing Gröbner Bases. Computational Commutative and Non-Commutative Algebraic Geometry. IOS Press, Amsterdam, 2005, pp.199–225.
[4] J.-C.Faugère and A.Joux. Algebraic Cryptanalysis of Hidden Field Equations (HFE) Using Gröbner Bases. LNCS 2729, Springer-Verlag, 2003, pp.44–60.
[5] V.P.Gerdt and M.V.Zinin. A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings. Proceedings of ISSAC 2008, ACM Press, 2008, pp.95–102.
[6] V.P.Gerdt and M.V.Zinin. Involutive Method for Computing Gröbner Bases over F2. Programming and Computer Software, Vol.34, No. 4, 2008, 191–203.
[7] Vladimir Gerdt, Mikhail Zinin and Yuri Blinkov. On computation of Boolean involutive bases, Proceedings of International Conference Polynomial Computer Algebra 2009, pp. 17-24 (International Euler Institute, April 7-12, 2009, St. Peterburg, Russia)
Up | Next | Prev | PrevTail | Front |