Parallel-Distributed Software Implementation of Buchberger Algorithm

Authors: Praloy Kumar Biswas, Prof. Dipanwita Roy Chowdhury

Abstract:

Grobner basis calculation forms a key part of computational commutative algebra and many other areas. One important ramification of the theory of Grobner basis provides a means to solve a system of non-linear equations. This is why it has become very important in the areas where the solution of non-linear equations is needed, for instance in algebraic cryptanalysis and coding theory. This paper explores on a parallel-distributed implementation for Grobner basis calculation over GF(2). For doing so Buchberger algorithm is used. OpenMP and MPI-C language constructs have been used to implement the scheme. Some relevant results have been furnished to compare the performances between the standalone and hybrid (parallel-distributed) implementation.

Keywords: Grobner basis, Buchberger Algorithm, Distributed- Parallel Computation, OpenMP, MPI.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073058

References:

[1] Url: http://www.sagemath.org/doc/reference/sage/rings/polynomial/pbori.html.
[2] Gregory V. Bard. Algebraic Cryptanalysis. Springer, New York, USA, 2009.
[3] B. Buchberger. Gr¨obner-Bases: An Algorithmic Method in Polynomial Ideal Theory. Reidel Publishing Company, Dodrecht - Boston - Lancaster, 1985.
[4] Soumen Chakrabarti and Katherine A. Yelick. Distributed data structures and algorithms for grobner basis computation. Lisp and Symbolic Computation, 7(2-3):147-172, 1994.
[5] Jean charles Faug`ere and Sylvain Lachartre. Parallel gaussian elimination for grbner bases computations in finite fields. In ACM proceedings of The International Workshop on Parallel and Symbolic Computation (PASCO), pages 1-10. ACM, 2010.
[6] Donal O-Shea. David Cox, John Little. Ideals, Varieties, and Algorithms. Springer Verlag, 1992.
[7] Jean Charles Faug`ere. A new efficient algorithm for computing grobner bases (f4). In Journal of Pure and Applied Algebra, pages 75-83. ACM Press, 1999.
[8] Jean Charles Faug`ere. A new efficient algorithm for computing grobner bases without reduction to zero (f5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC -02, pages 75-83, New York, NY, USA, 2002. ACM.
[9] Gerhard Wellein. George Hager. Introduction to High Performance Computing for Scientists and Engineers. CRC Press (Taylor & Francis Group)., New York, USA, 2011.
[10] Heinz Kredel. Distributed parallel groebner bases computation. In CISIS, pages 518-524, 2009.
[11] Anton Leykin. On parallel computation of gr¨obner bases. In ICPP Workshops, pages 160-164, 2004.
[12] Ernst W. Mayr. Some complexity results for polynomial ideals. JOURNAL OF COMPLEXITY 13, ARTICLE NO. CM970447, pages 303-325, 1997.
[13] Gert-Martin Grenel Markus Wedler Oliver Wienand. Michael Brickenstein, Alexander Dreyer. New developments in the theory of grobner bases and application to formal verification. Joournal of Pure and Applied Algebra. Vol. 213, pages 1612-1635, 2008.
[14] Michael J. Quinn. PARALLEL PROGRAMMING in C with MPI and OpenMP. TATA McGRAW-HILL Education Pvt. Ltd., New Delhi, India, 2010.
[15] Havvard Raddum. Cryptanalytic results on trivium. The eStream Project, 2006.
[16] Yosuke Sato. Parallel computation of boolean grobner bases. SIGSAM Bull., 34(1):27-28, March 2000.
[17] Hemal V. Shah and Jose A. B. Fortes. Tree structured grobner basis computation on parallel machines. In ECE Technical Reports. Paper 199, 1994.
[18] Philippe Loustaunau. Williums W. Adams. An Introduction to Grobner Basis. American Mathematical Society (AMS), 1994.