A solution to the extended gcd problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A solution to the extended gcd problem

Full text

Pdf (587 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1995 international symposium on Symbolic and algebraic computation table of contents

Montreal, Quebec, Canada

Pages: 248 - 253

Year of Publication: 1995

ISBN:0-89791-699-9

Authors

Bohdan S. Majewski	Department of Computer Science, University of Queensland, Queensland 4072, Australia
George Havas	Department of Computer Science, University of Queensland, Queensland 4072, Australia

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 29, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/220346.220377 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	W.A. Blankinship. A new version of the Euclidean algorithm. Amer. Math. Mon., 70:742-745, 1963.
	2	Gordon H. Bradley, Algorithm and bound for the greatest common divisor of n integers, Communications of the ACM, v.13 n.7, p.433-436, July 1970 [doi>10.1145/362686.362694]
	3	A.J. Brentjes, Multi-dimensional continued fraction algorithms, Mathematisch Centrum, Amsterdam 1981.
	4	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	5	G. Havas and B.S. Majewski. Integer matrix diagonalization. Technical Report TR0277, The University of Queensland, Brisbane, 1993.
	6	G. Havas and B.S. Majewski. Hermite normal form computation for integer matrices. Congressus Numerantium, 105:184-193, 1994.
	7	G. Havas, B.S. Majewski, and K.R. Matthews. Extended gcd algorithms. Technical Report TR0302, The University of Queensland, Brisbane, 1994.
	8	Costas 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 Journal on Computing, v.18 n.4, p.658-669, Aug. 1989 [doi>10.1137/0218045]
	9	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	10	R.J. Levit. A minimum solution to a diophantine equation. American Math. Mon., 63:647-651, 1956.
	11	Bohdan S. Majewski , George Havas, The complexity of greatest common divisor computations, Proceedings of the First International Symposium on Algorithmic Number Theory, p.184-193, May 06-09, 1994
	12	B.S. Majewski and G. Havas. Extended gcd calculation. Technical Report TR0325, The University of Queensland, Brisbane, 1995.
	13	D.J. Rose and R.E. Tarjan. Algorithmic aspects of vertex elimination on directed graphs. SIAM J. Appl. Math., 34:176-197, 1978.

CITED BY 4

	Xin Gui Fang , George Havas, On the worst-case complexity of integer Gaussian elimination, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.28-31, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Mark Giesbrecht, Efficient parallel solution of sparse systems of linear diophantine equations, Proceedings of the second international symposium on Parallel symbolic computation, p.1-10, July 20-22, 1997, Maui, Hawaii, United States
	Thierry Gautier , Jean-Louis Roch, NC² computation of gcd-free basis and application to parallel algebraic numbers computation, Proceedings of the second international symposium on Parallel symbolic computation, p.31-37, July 20-22, 1997, Maui, Hawaii, United States
	Arne Storjohann, A solution to the extended GCD problem with applications, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.109-116, July 21-23, 1997, Kihei, Maui, Hawaii, United States