Some Applications of Gröbner bases

Authors: Hassan Noori, Abdolali Basiri, Sajjad Rahmany

Abstract:

In this paper we will introduce a brief introduction to theory of Gr¨obner bases and some applications of Gr¨obner bases to graph coloring problem, automatic geometric theorem proving and cryptography.

Keywords: Gr¨obner bases, Application of Gr¨obner bases, Automatic Geometric Theorem Proving, Graph Coloring, Cryptography.

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

References:

[1] W. Adams, "Minicourse, Second Lecture Applications of Gr¨obner Bases". University of Maryland, March, 2005.
[2] W. Adams, and P. Loustaunau, "An Introduction to Gr¨obner Bases". AMS, Providence, Rhode Island, 1994.
[3] S. Arita, "Algorithms for computations in Jacobian group of Cab curve and their application to discrete-log based public key cryptosystems". IEICE Transactions, J82-A(8):12911299, 1999. In Japanese. English translation in the proceedings of the Conference on The Mathematics of Public Key Cryptography, Toronto 1999.
[4] A. Basiri, A. Enge, J.-C. Faugere, and N. Gurel. "Fast arithmetic for superelliptic cubics".
[5] A. Basiri, A. Enge, J.-C. Faugere, and N. Gurel. "Implementing the arithmetic of C34 curves". In Proceedings of ANTS-VI, Lecture Notes in Computer Science, pages 87101. Springer-Verlag, June 2004.
[6] M.-L. Bauer. The arithmetic of certain cubic function fields. Preprint, 2001.
[7] B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German). PhD thesis, University of Innsbruck, Austria, 1965.
[8] D. Cox, J. Little, and D. O-Shea, Ideals, Varieties, and Algorithms. Springer: New York, 1997.
[9] J.-C. Faugere, A new efficient algorithm for computing Gr¨obner bases (F4), Effective methods in algebraic geometry (Saint-Malo, 1998), J. Pure Appl. Algebra 139 no. 1-3 (1999) 6188.
[10] J.-C. Faugere, A new efficient algorithm for computing Gr¨obner bases without reduction to zero (F5), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, 7583 (electronic), ACM, New York, 2002.
[11] J.-C. Faugere, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional Gr¨obner bases by change of ordering. Journal of Symbolic Computation, 16:329344, 1993.
[12] S.-D. Galbraith, S. Paulus, and N.-P. Smart. Arithmetic on superelliptic curves. Mathematics of Computation, 71(237):393405, 2002.
[13] A. Heck, A Bird-s-Eye View of Gr¨obner Bases, CAN Expertise Center, 1996.
[14] R. Harasawa and J. Suzuki. Fast Jacobian group arithmetic on Cab curves. In Wieb Bosma, editor, Algorithmic Number Theory ANTSIV, volume 1838 of Lecture Notes in Computer Science, pages 359376, Berlin, 2000. Springer-Verlag.
[15] J. Verschelde, Lecture Note in Analytic Symbolic Computation, UIC, Dept. of Math, Stat & CS, spring 2009.
[16] S. Paulus. Lattice basis reduction in function fields. In J. P. Buhler, editor, Algorithmic Number Theory ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 567575, Berlin, 1998. Springer-Verlag.
[17] R. Scheidler, Ideal arithmetic and infrastructure in purely cubic function fields. Journal de Theorie des Nombres de Bordeaux, 13:609631, 2001.