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)

Short URL: ia.cr/2009/151

Discussion forum: Show discussion | Start new discussion