Abstract
Extended gcd computation is interesting itself. It also plays a fundamental role in other calculations. We present a new algorithm for solving the extended gcd problem. This algorithm has a particularly simple description and is practical. It also provides refined bounds on the size of the multipliers obtained.
Partially supported by the Natural Sciences and Engineering Research Council (Canada) and Fonds pour la Formation de Chercheurs et l'Aide à la Recherche (Québec).
Partially supported by the Australian Research Council.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W.A. Blankinship. A new version of the Euclidean algorithm. Amer. Math. Mon., 70:742–745, 1963.
G.H. Bradley. Algorithm and bound for the greatest common divisor of n integers. Commun. ACM, 13:433–436, 1970.
G. Havas and B.S. Majewski. Integer matrix diagonalization. J. Symbolic Comput., to appear.
G. Havas and B.S. Majewski. Hermite normal form computation for integer matrices. Congressus Numerantium, 105:184–193, 1994.
G. Havas and B.S. Majewski. A hard problem which is almost always easy. In Algorithms and Computation, Lecture Notes in Computer Science 1004, 216–223, 1995.
G. Havas, B.S. Majewski and K.R. Matthews. Extended gcd algorithms. Technical Report TR0302, The University of Queensland, Brisbane, 1994.
C.S. Iliopoulos. Worst case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix. SIAM J. Computing, 18:658–669, 1989.
D.E. Knuth. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading, Mass., 2nd edition, 1973.
B.S. Majewski and G. Havas. The complexity of greatest common divisor computations. In Algorithmic Number Theory, Lecture Notes in Computer Science 877, 184–193, 1994.
B.S. Majewski and G. Havas. A solution to the extended gcd problem. In ISSAC'95 (Proc. 1995 Internat. Sympos. Symbolic Algebraic Comput.), ACM Press, New York, 248–253, 1995.
B.S. Majewski and G. Havas. Extended gcd calculation. Congressus Numerantium, 111:104–114, 1995.
M-H. Mathieu and D. Ford. On p-adic Computation of the Rational Form of a Matrix, J. Symbolic Comput., 10:453–464, 1990.
P. Ozello. Calcul Exact des formes de Jordan et de Frobenius d'une Matrice. Doctoral Thesis, University of Grenoble, 1987.
M.S. Waterman. Multidimensional greatest common divisor and Lehmer algorithms. BIT, 17:465–478, 1977.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ford, D., Havas, G. (1996). A new algorithm and refined bounds for extended gcd computation. In: Cohen, H. (eds) Algorithmic Number Theory. ANTS 1996. Lecture Notes in Computer Science, vol 1122. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61581-4_50
Download citation
DOI: https://doi.org/10.1007/3-540-61581-4_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61581-1
Online ISBN: 978-3-540-70632-8
eBook Packages: Springer Book Archive