Parallel-Distributed Software Implementation of Buchberger Algorithm

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.

Authors:

• Praloy Kumar Biswas
• Prof. Dipanwita Roy Chowdhury

Keywords:

• Grobner basis
• Buchberger Algorithm
• Distributed- Parallel Computation
• OpenMP
• MPI.

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.