## Cryptology ePrint Archive: Report 2009/151

**Euclid's Algorithm, Guass' Elimination and Buchberger's Algorithm**

*Shaohua Zhang*

**Abstract: **It is known that Euclid's algorithm,
Guass' elimination and Buchberger's algorithm play important roles
in algorithmic number theory, symbolic computation and cryptography,
and even in science and engineering. The aim of this paper is to
reveal again the relations of these three algorithms, and, simplify
Buchberger's algorithm without using multivariate division
algorithm. We obtain an algorithm for computing the greatest common
divisor of several positive integers, which can be regarded as the
generalization of Euclid's algorithm. This enables us to re-find the
Guass' elimination and further simplify Buchberger's algorithm for
computing Gr\"{o}bner bases of polynomial ideals in modern
Computational Algebraic Geometry.

**Category / Keywords: **Euclid's algorithm, Guass' elimination, multivariate polynomial, Gr\"{o}bner bases, Buchberger's algorithm

**Date: **received 9 Mar 2009, last revised 14 Jan 2010

**Contact author: **shaohuazhang at mail sdu edu cn

**Available format(s): **PDF | BibTeX Citation

**Note: **The paper have been improved.

**Version: **20100114:115438 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]