Abstract
In this paper, an involutive algorithm for computation of Gröbner bases for polynomial ideals in a ring of polynomials in many variables over the finite field \( \mathbb{F}_2 \) with the values of variables belonging of \( \mathbb{F}_2 \) is considered. The algorithm uses Janet division and is specialized for a graded reverse lexicographical order of monomials. We compare efficiency of this algorithm and its implementation in C++ with that of the Buchberger algorithm, as well as with the algorithms of computation of Gröbner bases that are built in the computer algebra systems Singular and CoCoA and in the FGb library for Maple. For the sake of comparison, we took widely used examples of computation of Gröbner bases over ℚ and adapted them for \( \mathbb{F}_2 \). Polynomial systems over \( \mathbb{F}_2 \) with the values of variables in \( \mathbb{F}_2 \) are of interest, in particular, for modeling quantum computation and a number of cryptanalysis problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Buchberger, B., Algorithm for Finding a Basis for the Residue Class Ring of Zero-Dimensional Polynomial Ideal, PhD Dissertation, Innsbruck, Univ. of Innsbruck, Inst. for Mathematics, 1965 (in German).
Buchberger, B., Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, Recent Trends in Multidimensional System Theory, Bose, N.K., Ed., Dordrecht: Reidel, 1985, pp. 184–232.
Gerdt, V.P. and Blinkov, Yu.A., Involutive Bases of Polynomial Ideals, Math. Comput. Simulation, 1998, vol. 45, pp. 519–542. arXiv:math.AC/9912027; Minimal Involutive Bases. Math. Comput. Simulation, pp. 543–560. arXiv:math.AC/9912029.
Gerdt, V.P., Involutive Algorithms for Computing Gröbner Bases, Computational Commutative and Non-Commutative Algebraic Geometry, Cojocaru, S., Pfister, G., and Ufnarovski, V., Eds., Amsterdam: IOS, 2005, pp. 199–225. arXiv:math.AC/0501111.
Faugère, J.C., A New Efficient Algorithm for Computing Gröbner Bases (F 4), Pure Applied Algebra, 1999, vol. 139, nos. 1–3, pp. 61–68.
Faugère, J.C., A New Efficient Algorithm for Computing Gröbner Bases without Reduction to Zero (F 5), Proc. of ISSAC 2002, New York: ACM, 2002, pp. 75–83.
Seiler, W.M., Involution—The Formal Theory of Differential Equations and Its Applications in Computer Algebra and Numerical Analysis, Habilitation Thesis, Dept. of Mathematics, University of Manheim, 2002.
Gerdt, V.P., Completion of Linear Differential Systems to Involution, Computer Algebra in Scientific Computing (CASC’99), Ganzha, V.G., Mayr, E.W., and Vorozhtsov, E.V., Eds., Berlin: Springer, 1999, pp. 115–137.
Gerdt, V.P., Blinkov, Yu.A., and Mozzhilkin, V.V., Gröbner Bases and Generation of Difference Schemes for Partial Differential Equations, Symmetry, Integrability and Geometry: Methods and Applications (SIGMA), 2006, vol. 2, paper 051, arXiv:math.RA/0605334.
Gerdt, V.P., Kragler, R., and Prokopenya, A.N., A Mathematica Package for Construction of Circuit Matrices in Quantum Computation. Computer Algebra and Differential Equations (CADE 2007), Proc. of Int. Workshop, Turku, Finland, 2007. To appear.
Levy-dit-Vehel, F. and Perret, L.L., Polynomial Equivalence Problems and Applications to Multivariate Crypto-systems, Report no. 5119, INRIA, 2004, http://www.inria.fr/rrrt/rr-5119.html.
Faugère, J.C., Algebraic Cryptanalysis of HFE Using Gröbner Bases, INRIA Report RR-4738, 2003, http://www.inria.fr/rrrt/rr-4738.html.
Faugère, J.C. and Joux, A., Algebraic Cryptanalysis of Hidden Field Equations (HFE) Using Gröbner Bases, LNCS, Springer, 2003, vol. 2729, pp. 44–60.
Apel, J. and Hemmecke, R., Detecting Unnecessary Reductions in an Involutive Basis Computation, RISC Linz Report Series 02-22, 2002.
Gerdt, V.P., Yanovich, D.A., and Blinkov, Yu.A., Fast Search for the Janet Divisor, Programmirovanie, 2001, no. 1, pp. 32–36 [Programming Comput. Software (Engl. Transl.), 2001, vol. 27, no. 1, pp. 22–24].
Greuel, G.-M., Pfister, G., and Schönemann, H., Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005, http://www.singular.unikl.de.
http://www.-sop.inria.fr/saga/POL; http://www.math.uic.edu/:_jan/demo.html.
Kornyak, V.V., On Compatibility of Discrete Relations, LNCS, Springer, 2005, vol. 3718, pp. 272–284, arXiv:math-ph/0504048.
Gerdt, V.P. and Yanovich, D.A., Effectiveness of Involutive Criteria in Computation of Polynomial Janet Bases, Programmirovanie, 2006, no. 3, pp. 17–21 [Programming Comput. Software (Engl. Transl.), 2006, vol. 32, no. 3, pp. 134–138].
Gerdt, V.P. and Blinkov, Yu.A., On Selection of Nonmultiplicative Prolongations in Computation of Janet Bases, Programmirovanie, 2007, no. 2, pp. 34–43 [Programming Comput. Software (Engl. Transl.), 2007, vol. 33, no. 3, pp. 147–153].
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © V.P. Gerdt, M. V. Zinin, 2008, published in Programmirovanie, 2008, Vol. 34, No. 4.
Rights and permissions
About this article
Cite this article
Gerdt, V.P., Zinin, M.V. Involutive method for computing Gröbner bases over \( \mathbb{F}_2 \) . Program Comput Soft 34, 191–203 (2008). https://doi.org/10.1134/S0361768808040026
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0361768808040026