You are looking at a specific version 20100114:115438 of this paper. See the latest version.

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 algorithmGuass' eliminationmultivariate polynomialGröbner basesBuchberger'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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.