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

Shaohua Zhang

Paper 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öbner bases of polynomial ideals in modern Computational Algebraic Geometry.

Note: The paper have been improved.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Euclid's algorithm Guass' elimination multivariate polynomial Gröbner bases Buchberger's algorithm
Contact author(s): shaohuazhang @ mail sdu edu cn
History: 2010-01-14: revised; 2009-04-01: received; See all versions
Short URL: https://ia.cr/2009/151
License: CC BY

BibTeX

@misc{cryptoeprint:2009/151,
      author = {Shaohua Zhang},
      title = {Euclid's Algorithm, Guass' Elimination and Buchberger's Algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/151},
      year = {2009},
      url = {https://eprint.iacr.org/2009/151}
}