@article{Pitteway&Castle:1988,
	key = "Pitteway and Castle 1988",
	author = "M. L. V. Pitteway and C. M. A. Castle",
	title = "On the subtractive version of {Euclid's} algorithm",
	journal = BIMA,
	volume = 24,
	year = 1988,
	pages = "17-21"}

@article{Yao&Knuth:1975,
	key = "Yao and Knuth 1975",
	author = "A. C. Yao and D. E. Knuth",
	title = "Analysis of the subtractive algorithm for greatest common
divisors",
	journal = PNAS,
	year = 1975,
	volume = 72,
	pages = "4720-4722"}

@article{Zheng:1994,
	key = "Zheng 1994",
	author = "Z.-Y. Zheng",
	title = "On a theorem of H. [sic] Yao and D. Knuth",
	journal = ACTAMS,
	volume = 37,
	year = 1994,
	pages = "191-202",
	note = "In Chinese.  Reviewed in {\it Math.\ Reviews} 95h:11006."}

@book{Gardner:1971,
	key = "Gardner 1971",
	author = "M. Gardner",
	title = "The Sixth Book of Mathematical Games from
{\it Scientific American}",
	publisher = "Scribner",
	address = NY,
	year = 1971}

@article{Euler:1762,
	key = "Euler 1762",
	author = "L. Euler",
	title = "Specimen algorithmi singularis",
	journal = NCASP,
	volume = 9,
	year = 1762,
	pages = "53-69",
	note = "Reprinted in {\it Opera Omnia}, Ser.~1, Vol.~15, pp.~31--49"}

@article{Purdy:1983,
	key = "G. Purdy 1983",
	author = "G. B. Purdy",
	title = "A carry-free algorithm for finding the greatest
common divisor of two integers",
	journal = CMA,
	volume = 9,
	year = 1983,
	pages = "311-316"}

@article{Vahlen:1895,
	key = "Vahlen 1895",
	author = "K. Th. Vahlen",
	title = "{\"Uber} {N\"aherungswerthe} und {Kettenbr\"uche}",
	journal = JFRAM,
	volume = 115,
	year = 1895,
	pages = "221-233"}

@inproceedings{Norton:1985,
	key = "G. Norton 1985",
	author = "G. H. Norton",
	title = "Extending the binary gcd algorithm",
	booktitle = "AAECC-3",
	editor = "J. Calmet",
	series = LNICS,
	volume = 229,
	year = "1985",
	pages = "363-372"}

@inproceedings{Norton:1987,
	key = "G. Norton 1987",
	author = "G. H. Norton",
	title = "A shift-remainder gcd algorithm",
	booktitle = "AAECC-5",
	editor = "L. Huguet and A. Poli",
	series = LNICS,
	volume = 356,
	year = "1987",
	pages = "350-356"}

@article{Mays:1987,
	key = "Mays 1987",
	author = "M. E. Mays",
	title = "Iterating the division algorithm",
	journal = FQ,
	volume = 25,
	year = 1987,
	pages = "204-213"}

@article{Harris:1970a,
	key = "V. Harris 1970a",
	author = "V. C. Harris",
	title = "An algorithm for finding the greatest common divisor",
	journal = FQ,
	volume = 8,
	year = 1970,
	pages = "102-103"}

@article{Harris:1970b,
	key = "V. Harris 1970b",
	author = "V. C. Harris",
	title = "Note on the number of divisions required in finding
the greatest common divisor",
	journal = FQ,
	volume = 8,
	year = 1970,
	pages = "104"}

@article{Collins:1974a,
	key = "G. Collins 1974a",
	author = "G. E. Collins",
	title = "The computing time of the {Euclidean} algorithm",
	journal = SIAMJC,
	volume = 3,
	year = "{\noopsort{1974a}}1974",
	pages = "1-10"}

@article{Stein:1967,
	key = "J. Stein 1967",
	author = "J. Stein",
	title = "Computational problems associated with {Racah} algebra",
	journal = JCP,
	volume = 1,
	year = 1967,
	pages = "397-405"}

@article{Dupre:1846,
	key = "Dupr\'e 1846",
	author="A. Dupr\'e",
	title="Sur le nombre de divisions \`a effectuer pour obtenir le
plus grand commun diviseur entre deux nombres entiers",
	journal = JMPA,
	volume = 11,
	year = 1846,
	pages = "41-64"}

@article{Lehmer:1938,
	key = "D. H. Lehmer 1938",
	author = "D. H. Lehmer",
	title = "Euclid's algorithm for large numbers",
	journal = AMM,
	volume = 45,
	year = 1938,
	pages = "227-233"}

@incollection{Brent:1976a,
	key = "Brent 1976a",
	author = "R. P. Brent",
	title = "Analysis of the binary {Euclidean} algorithm",
	booktitle = "Algorithms and Complexity:  New Directions and
	Recent Results",
	editor = "J. F. Traub",
	publisher = AP,
	address = NY,
	year = 1976,
	pages = "321-355"}

@article{Chatland:1949,
	key = "Chatland 1949",
	author = "H. Chatland",
	title = "On the {Euclidean} algorithm in quadratic number fields",
	journal = BAMS,
	volume = 55,
	year = 1949,
	pages = "948-953"}

@article{Chatland&Davenport:1950,
	key = "Chatland and Davenport 1950",
	author = "H. Chatland and H. Davenport",
	title = "Euclid's algorithm in real quadratic fields",
	journal = CJM,
	volume = 2,
	year = 1950,
	pages = "289-296"}

@article{Lame:1844,
	key = "{Lam\'e} 1844",
	author = "G. Lam\'e",
	title = "Note sur la limite du nombre des divisions dans la recherche
du plus grand commun diviseur entre deux nombres entiers",
	journal = CRASP,
	volume = 19,
	year = 1844,
	pages = "867-870"}

@article{Rolletschek:1986,
	key = "Rolletschek 1986",
	author = "H. Rolletschek",
	title = "On the number of divisions of the {Euclidean} algorithm applied
to {Gaussian} integers",
	journal = JSC,
	volume = 2,
	year = 1986,
	pages = "261-291"}

@article{Floyd&Knuth:1990,
	key = "Floyd and Knuth 1990",
	author = "R. W. Floyd and D. E. Knuth",
	title = "Addition machines",
	journal = SIAMJC,
	volume = 19,
	year = 1990,
	pages = "329-340"}

@article{Kaltofen&Rolletschek:1989,
	key = "Kaltofen and Rolletschek 1989",
	author = "E. Kaltofen and H. Rolletschek",
	title = "Computing greatest common divisors and factorizations
in quadratic number fields",
	journal = MC,
	year = 1989,
	volume = 53,
	pages = "697-720"}

@article{Chor&Goldreich:1990,
	key = "Chor and Goldreich 1990",
	author = "B. Chor and O. Goldreich",
	title = "An improved parallel algorithm for integer gcd",
	journal = "Algorithmica",
	year = 1990,
	volume = 5,
	pages = "1-10"}

@techreport{Collins:1968,
	key = "G. Collins 1968",
	author = "G. E. Collins",
	title = "Computing time analyses for some arithmetic and 
algebraic algorithms",
	institution = "University of Wisconsin, Madison; Computer Sciences",
	number = 36,
	month = "July",
	year = 1968,
	note = "Appeared in {\it Proc. 1968 Summer Institute on Symbolic
Mathematical Computations}, IBM Federal Systems Center, 1968, pp.~195--231"}

@article{Samuel:1971,
	key = "Samuel 1971",
	author = "P. Samuel",
	title = "About {Euclidean} rings",
	journal = JALG,
	volume = 19,
	year = 1971,
	pages = "282-301"}

@book{Kronecker:1901,
	key = "Kronecker 1901",
	author = "L. Kronecker",
	title = "Vorlesungen {\"uber} Zahlentheorie",
	volume = 1,
	publisher = "Teubner",
	year = "1901",
	note = "Reprinted by Springer-Verlag, 1978"}

@article{Goodman&Zaring:1952,
	key = "Goodman and Zaring 1952",
	author = "A. W. Goodman and W. M. Zaring",
	title = "Euclid's algorithm and the least-remainder algorithm",
	journal = AMM,
	volume = 59,
	year = 1952,
	pages = "156-159"}

@article{Bradley:1970,
	key = "Bradley 1970",
	author = "G. H. Bradley",
	title = "Algorithm and bound for the greatest common divisor
of $n$ integers",
	journal = CACM,
	volume = 13,
	year = 1970,
	pages = "433-436"}

@article{Blankinship:1963,
	key = "Blankinship 1963",
	author = "W. A. Blankinship",
	title = "A new version of the {Euclidean} algorithm",
	journal = AMM,
	volume = 70,
	year = 1963,
	pages = "742-745"}

@inproceedings{Caviness&Collins:1976,
	key = "Caviness and Collins 1976",
	author = "B. F. Caviness and G. E. Collins",
	title = "Algorithms for {Gaussian} integer arithmetic",
	booktitle = "Symsac '76:  Proceedings of the 1976 ACM Symposium
on Symbolic and Algebraic Computation",
	year = 1976,
	editor = "R. D. Jenks",
	pages = "36-45"}

@article{Muir:1878,
	key = "Muir 1878",
	author = "T. Muir",
	title = "Letter from {Mr. Muir} to {Professor Sylvester} on
the word continuant",
	journal = AJM,
	volume = 1,
	year = 1878,
	pages = "344"}

@article{Muir:1874,
	key = "Muir 1874",
	author = "T. Muir",
	title = "Continuants--a new special class of determinants",
	journal = PRSE,
	volume = 8,
	year = "1872-5",
	pages = "229-236"}

@article{Cole&Davie:1969,
	key = "Cole and Davie 1969",
	author = "A. J. Cole and A. J. T. Davie",
	title = "A game based on the {Euclidean} algorithm and a 
winning strategy for it",
	journal = MG,
	volume = 53,
	year = 1969,
	pages = "354-357"}

@incollection{Knuth:1971,
	key = "Knuth 1971",
	author = "D. E. Knuth",
	title = "The analysis of algorithms",
	booktitle = "Actes du {Congr\`es} International des
{Math\'ematiciens}, 1970",
	volume = 3,
	year = 1971,
	publisher = "Gauthier-Villars",
	address = "Paris",
	pages = "269-274"}

@article{Waterman:1977,
	key = "Waterman 1977",
	author = "M. S. Waterman",
	title = "Multidimensional greatest common divisor and {Lehmer}
algorithms",
	journal = BIT,
	volume = 17,
	year = 1977,
	pages = "465-478"}

@book{Uspensky&Heaslet:1939,
	key = "Uspensky and Heaslet 1939",
	author = "J. V. Uspensky and M. A. Heaslet",
	title = "Elementary Number Theory",
	publisher = "McGraw-Hill",
	address = NY,
	year = 1939}

@incollection{Brent&Kung:1983,
	key = "Brent and Kung 1983",
	author = "R. P. Brent and H. T. Kung",
	title = "Systolic {VLSI} arrays for linear-time {GCD} computation",
	booktitle = "{VLSI '83}",
	editor = "F. Anceau and E. J. Aas",
	publisher = "Elsevier Science Publishers B. V.",
	year = 1983,
	pages = "145-154"}

@misc{Zavrotsky:1961,
	key = "Zavrotsky 1961",
	author = "A. Zavrotsky",
	title = "Greatest common divisor finder",
	note = "April 11, 1961, U. S. patent 2,978,816; filed February 4, 1960"}

@article{Kannan&Miller&Rudolph:1987,
	key = "Kannan, Miller, and Rudolph 1987",
	author = "R. Kannan and G. L. Miller and L. Rudolph",
	title = "Sublinear parallel algorithm for computing the
greatest common divisor of two integers",
	journal = SIAMJC,
	volume = 16,
	year = 1987,
	pages = "7-16"}

@article{Hurwitz:1887,
	key = "Hurwitz 1887",
	author = "A. Hurwitz",
	title = "{\"Uber} die {Entwicklung} complexer {Gr\"ossen} in
{Kettenbr\"uche}",
	journal = ACTAM,
	volume = 11,
	year = 1887,
	pages = "187-200",
	note = "Reprinted in {\it Werke,} Vol.~II, pp.~72--83"}

@book{Bachmann:1902,
	key = "Bachmann 1902",
	author = "P. Bachmann",
	title = "Niedere Zahlentheorie",
	publisher = "Teubner",
	address = "Leipzig",
	year = 1902,
	volume = "I",
	note = "Reprinted by Chelsea, New York, 1968"}

@article{Bojanczyk&Brent:1987,
	key = "Bojanczyk and Brent 1987",
	author = "A. W. Bojanczyk and R. P. Brent",
	title = "A systolic algorithm for extended {GCD} computation",
	journal = CMA,
	volume = 14,
	year = 1987,
	pages = "233-238"}

@article{Schaefer:1975,
	key = "Schaefer 1975",
	author = "P. Schaefer",
	title = "An algorithm for finding the {GCD} of a finite set of
integers",
	journal = "Delta (Waukesha)",
	volume = 5,
	year = 1975,
	pages = "19-27"}

@article{van.Trigt:1978,
	key = "van Trigt 1978",
	author = "Trigt, C. van",
	title = "Worst-case analysis of algorithms. {A. Some} g.c.d algorithms",
	journal = PJR,
	volume = 33,
	year = 1978,
	pages = "66-77"}

@incollection{Nagata:1978,
	key = "Nagata 1978",
	author = "M. Nagata",
	title = "On {Euclid} algorithm",
	booktitle = "C. P. Ramanujam -- A Tribute",
	publisher = "Narosa Publishing House",
	address = "New Delhi",
	year = 1978}

@article{CohnP:1961,
	key = "P. Cohn 1961",
	author = "P. M. Cohn",
	title = "On a generalization of the {Euclidean} algorithm",
	journal = PCPS,
	volume = 57,
	year = 1961,
	pages = "18-30"}

@article{Eggleton:1987,
	key = "Eggleton 1987",
	author = "R. B. Eggleton",
	title = "Common factors of integers:  a graphic view",
	journal = DM,
	volume = 65,
	year = 1987,
	pages = "141-147"}

@article{Rosser:1942,
	key = "Rosser 1942",
	author = "J. B. Rosser",
	title = "A generalization of the {Euclidean} algorithm to
several dimensions",
	journal = DMJ,
	volume = 9,
	year = 1942,
	pages = "59-95"}

@article{Purdy&Purdy:1990a,
	key = "C. Purdy and Purdy 1990a",
	author = "C. N. Purdy and G. B. Purdy",
	title = "The area-time complexity of the greatest common divisor problem:
a lower bound",
	journal = IPL,
	volume = 34,
	year = "{\noopsort{1990a}}1990",
	pages = "43-46"}

@inproceedings{Bach&Driscoll&Shallit:1990,
	key = "Bach, Driscoll, and Shallit 1990",
	author = "E. Bach and J. Driscoll and J. O. Shallit",
	title = "Factor refinement",
	booktitle = SODA90,
	year = 1990,
	pages = "201-211"}

@article{Shallit:1979a,
	key = "Shallit 1979a",
	author = "J. O. Shallit",
	title = "Simple continued fractions for some irrational numbers",
	journal = JNT,
	volume = 11,
	year = 1979,
	pages = "209-217"}

@article{Shallit:1982,
	key = "Shallit 1982",
	author = "J. O. Shallit",
	title = "Simple continued fractions for some irrational numbers, {II}",
	journal = JNT,
	volume = 14,
	year = 1982,
	pages = "228-231"}

@article{Shallit:1986,
	key = "Shallit 1986",
	author = "J. O. Shallit",
	title = "Metric theory of {Pierce} expansions",
	journal = FQ,
	volume = 24,
	year = 1986,
	pages = "22-40"}

@article{Epasinghe:1985,
	key = "Epasinghe 1985",
	author = "P. W. Epasinghe",
	title = "Euclid's algorithm and the {Fibonacci} numbers",
	journal = FQ,
	volume = 23,
	year = 1985,
	pages = "177-179"}

@techreport{Mansour&Schieber&Tiwari:1988,
	key = "Mansour, Schieber, and Tiwari 1988",
	author = "Y. Mansour and B. Schieber and P. Tiwari",
	title = "A lower bound for integer greatest common divisor
computations",
	institution = "IBM Research Division, Yorktown Heights",
	number = "RC 14271",
	month = "December",
	year = 1988}

@article{Mansour&Schieber&Tiwari:1991a,
	key = "Mansour, Schieber, and Tiwari 1991a",
	author = "Y. Mansour and B. Schieber and P. Tiwari",
	title = "A lower bound for integer greatest common divisor
computations",
	journal = JACM,
	volume = 38,
	pages = "453-471",
	year = 1991}

@article{Mansour&Schieber&Tiwari:1991b,
	key = "Mansour, Schieber, and Tiwari 1991b",
	author = "Y. Mansour and B. Schieber and P. Tiwari",
	title = "Lower bounds for computations with the floor
operation",
	journal = SIAMJC,
	volume = 20,
	year = 1991,
	pages = "315-327"}

@article{Marcus:1981,
	key = "Marcus 1981",
	author = "D. A. Marcus",
	title = "An alternative to {Euclid's} algorithm",
	journal = AMM,
	volume = 88,
	year = 1981,
	pages = "280-283"}

@article{Shea:1973,
	key = "Shea 1973",
	author = "D. D. Shea",
	title = "On the number of divisions needed in finding the 
greatest common divisor",
	journal = FQ,
	volume = 11,
	year = 1973,
	pages = "508-510"}

@article{Daykin:1970,
	key = "Daykin 1970",
	author = "D. E. Daykin",
	title = "An addition algorithm for greatest common divisor",
	journal = FQ,
	volume = 8,
	year = 1970,
	pages = "347-349"}

@article{Harris:1974,
	key = "V. Harris 1974",
	author = "V. C. Harris",
	title = "On {Daykin's} algorithm for finding the g.c.d.",
	journal = FQ,
	volume = 12,
	year = 1974,
	pages = "80"}

@article{Brown&Duncan:1971,
	key = "Brown and Duncan 1971",
	author = "Brown, Jr., J. L. and R. L. Duncan",
	title = "The least remainder algorithm",
	journal = FQ,
	volume = 9,
	year = 1971,
	pages = "347-350,401"}

@article{Weinstock:1960,
	key = "Weinstock 1960",
	author = "R. Weinstock",
	title = "Greatest common divisor of several integers and an
associated linear {Diophantine} equation",
	journal = AMM,
	volume = 67,
	year = 1960,
	pages = "664-667"}

@article{Abramov:1979,
	key = "Abramov 1979",
	author = "S. A. Abramov",
	title = "Some estimates related to the {Euclidean} algorithm",
	journal = ZVMIMF,
	volume = 19,
	year = 1979,
	pages = "756-760",
	note = "English translation in {\it U.S.S.R. Comput. Maths. Math.
Phys.} {\bf 19} (1979) 207--212."}

@article{Mandelbaum:1988,
	key = "Mandelbaum 1988",
	author = "D. M. Mandelbaum",
	title = "New binary {Euclidean} algorithms",
	journal = ELETT,
	volume = 24,
	year = 1988,
	pages = "857-858"}

@incollection{Yun&Zhang:1986,
	key = "Yun and Zhang 1986",
	author = "D. Y. Y. Yun and C. N. Zhang",
	title = "A fast carry-free algorithm and hardware design for
extended integer gcd computation",
	booktitle = "Proc. 1986 Symposium on Symbolic and Algebraic
Computation:  SYMSAC '86",
	editor = "B. W. Char",
	publisher = "ACM",
	year = 1986,
	pages = "82-84"}

@article{Rolletschek:1990,
	key = "Rolletschek 1990",
	author = "H. Rolletschek",
	title = "Shortest division chains in imaginary quadratic number
fields",
	journal = JSC,
	volume = 9,
	year = 1990,
	pages = "321-354"}

@inproceedings{Brent&Kung&Luk:1983,
	key = "Brent, Kung, and Luk 1983",
	author = "R. P. Brent and H. T. Kung and F. T. Luk",
	title = "Some linear time algorithms for systolic arrays",
	booktitle = "Information Processing 83:  Proc. IFIP 9th World
Computer Congress",
	publisher = "North-Holland",
	year = 1983,
	pages = "865-876"}

@article{Yang:1990,
	key = "Yang 1990",
	author = "K.-W. Yang",
	title = "Euclid's algorithm $=$ reverse {Gaussian} elimination",
	journal = MM,
	volume = 63,
	year = 1990,
	pages = "163-164"}

@article{Norton:1990,
	author = "G. H. Norton",
	key = "G. Norton 1990",
	title = "On the asymptotic analysis of the {Euclidean} algorithm",
	journal = JSC,
	volume = 10,
	year = 1990,
	pages = "53-58"}

@techreport{Bshouty:1991,
	key = "Bshouty 1991",
	author = "N. H. Bshouty",
	title = "Euclidean {GCD} algorithm is not optimal",
	year = 1991,
	month = "May",
	institution = "University of Calgary",
	number = "91/430/14"}

@article{Cremona&Landau:1990,
	key = "Cremona and Landau 1990",
	author = "J. Cremona and S. Landau",
	title = "Shrinking lattice polyhedra",
	journal = SIAMJDM,
	volume = 3,
	year = 1990,
	pages = "338-348"}

@article{von.Grosschmid:1911,
	key = "von Grosschmid 1911",
	author = "Grosschmid, L. von",
	title = "Ueber einen arithmetischen {Satz} von {Lam\'e}",
	journal = MNB,
	volume = 8,
	year = 1911,
	pages = "125-127"}

@inproceedings{Brent&Kung:1985,
	key = "Brent and Kung 1985",
	author = "R. P. Brent and H. T. Kung",
	title = "A systolic algorithm for integer {GCD} computation",
	editor = "K. Hwang",
	booktitle = "Proc. 7th Symp. Comp. Arith.",
	publisher = IEEEPR,
	year = 1985,
	pages = "118-125"}

@article{Leger:1837,
	key = "L{\'e}ger 1837",
	author = "E. {L\'eger}",
	title = "Note sur le partage d'une droite en moyenne et {extr\^eme}, et
sur un {probl\`eme} d'arithm{\'e}tique",
	journal = "Corresp. Math. Phys.",
	volume = 9,
	year = 1837,
	pages = "483-485"}

@incollection{Parikh&Matula:1991,
	key = "Parikh and Matula 1991",
	author = "S. N. Parikh and D. W. Matula",
	title = "A redundant binary {Euclidean} {GCD} algorithm",
	booktitle = "Proc. 10th IEEE Symp. Comp. Arith.",
	publisher = IEEEPR,
	editor = "P. Kornerup and D. W. Matula",
	year = 1991,
	pages = "220-225"}

@unpublished{Hensley:1992,
	key = "Hensley 1992",
	author = "D. Hensley",
	title = "The number of steps in the {Euclidean} algorithm",
	year = 1992,
	note = "Manuscript, dated October"}

@article{Finck:1842,
	key = "Finck 1842",
	author = "P. J. E. Finck",
	title = "Lettre",
	journal = NAM,
	volume = 1,
	year = 1842,
	pages = "353-355"}

@book{Finck:1841,
	key = "Finck 1841",
	author = "P. J. E. Finck",
	title = "{Trait\'e} {\'El\'ementaire} {d'Arithm\'etique} {\`a} l'Usage des
Candidats aux {\'Ecoles} {Sp\'eciales}",
	publisher = "Derivaux",
	address = "Strasbourg",
	year = 1841}

@book{Finck:1843,
	key = "Finck 1843",
	author = "P. J. E. Finck",
	title = "{Trait\'e} {\'El\'ementaire} {d'Arithm\'etique} {\`a} l'Usage des
Candidats aux {\'Ecoles} {Sp\'eciales}",
	publisher = "Derivaux",
	address = "Strasbourg",
	year = 1843,
	note = "2nd edition"}

@article{Finck:1845,
	key = "Finck 1845",
	author = "P. J. E. Finck",
	title = "Observations sur le {th\'eor\`eme} de {M. Lam\'e}, relativement
au plus grand commun diviseur, et nouvelle {d\'emonstration} de ce
{th\'eor\`eme}",
	journal = NAM,
	volume = 4,
	year = 1845,
	pages = "71-74"}

@misc{Shallit:1979b,
	key = "Shallit 1979b",
	author = "J. O. Shallit",
	title = "Integer Functions and Continued Fractions",
	howpublished = "A.B. Thesis, Princeton University",
	year = "{\noopsort{1979b}}1979"}

@article{Knopfmacher:1992,
	key = "Knopfmacher 1992",
	author = "A. Knopfmacher",
	title = "Elementary properties of the subtractive {Euclidean}
algorithm",
	journal = FQ,
	volume = 30,
	year = 1992,
	pages = "80-83"}

@article{Brun:1964,
	key = "Brun 1964",
	author = "V. Brun",
	title = "Euclidean algorithms and musical theory",
	journal = EM,
	volume = 10,
	year = 1964,
	pages = "125-137"}

@inproceedings{Linkriz&Pan:1992,
	key = "Lin-Kriz and Pan 1992",
	author = "Y. Lin-Kriz and V. Pan",
	title = "On parallel complexity of integer linear programming, {GCD}, and
the iterated mod function",
	booktitle = SODA92,
	year = 1992,
	pages = "124-137"}

@article{Moore:1992,
	key = "T. Moore 1992",
	author = "T. E. Moore",
	title = "On the least absolute remainder {Euclidean} algorithm",
	journal = FQ,
	volume = 30,
	year = 1992,
	pages = "161-165"}

@article{Sylvester:1883,
	key = "Sylvester 1883",
	author = "J. J. Sylvester",
	title = "On the number of fractions in their lowest terms whose
		 numerators and denominators are limited not to exceed
		 a certain number",
	journal = {\it Johns Hopkins Univ. Circulars},
	volume = "II",
	year = 1883,
	pages = "44-45",
	note = "Reprinted in {\it Collected Mathematical Papers}, Vol.~3, pp.~672--676"}

@article{Cesaro:1881b,
	key = "Ces{\`a}ro 1881b",
	author = "E. Ces{\`a}ro",
	title = "Question 75",
	journal = "Mathesis",
	volume = 1,
	year = "{\noopsort{1881b}}1881",
	comment = "Not in Opere Scelte",
	pages = "184"}

@article{Cesaro:1883,
	key = "Ces{\`a}ro 1883",
	author = "E. Ces{\`a}ro",
	title = "Sur divers questions d'arithm{\'e}tique",
	journal = "Mem. Soc. Roy. Sci. Li{\`e}ge",
	series = 2,
	volume = 10,
	year = 1883,
	pages = "1-350",
	note = "Reprinted in {\it Opere Scelte I}, Vol.~1, pp.~10--362"}

@article{Stieltjes:1890,
	key = "Stieltjes 1890",
	author = "T. J. Stieltjes",
	title = "Sur la {th\'eorie} des nombres",
	journal = "Ann. Fac. Sci. Toulouse",
	volume = 4,
	year = 1890,
	pages = "1-103",
	note = "Reprinted in {\it Oeuvres Compl\`etes},
		Vol.~II, pp.~279--377"}

@book{Alagic&Arbib:1978,
	key = "{Alagi\'c} and Arbib 1978",
	author = "S. {Alagi\'c} and M. A. Arbib",
	title = "The Design of Well-Structured and Correct Programs",
	publisher = SV,
	address = NY,
	year = 1978}

@article{CohnP:1991,
	key = "P. Cohn 1991",
	author = "P. M. Cohn",
	title = "Euclid's algorithm -- since {Euclid}",
	journal = MATHMED,
	volume = 19,
	number = 2,
	year = 1991,
	pages = "65-72"}

@article{Grossman:1924,
	key = "Grossman 1924",
	author = "H. Grossman",
	title = "On the number of divisions in finding a {G. C. D.}",
	journal = AMM,
	volume = 31,
	year = 1924,
	pages = "443"}

@article{Norton:1992,
	key = "G. Norton 1992",
	author = "G. H. Norton",
	title = "Computing {GCD's} by normalized division",
	journal = AAECC,
	volume = 2,
	year = 1992,
	pages = "275-295"}

@misc{Lagny:1733,
	key = "de Lagny 1733",
	author = "Lagny, T. F. de",
	title = "Analyse g\'en\'erale, ou m\'ethodes nouvelles pour r\'esoudre les probl\`emes
de tous les genres \& de tous les d\'egr\'es \`a l'infini",
	note = "{\it M\'emoires de l'Acad\'emie Royale des Sciences} (Paris) {\bf 11} (1733)"}

@article{Purdy&Purdy:1990b,
	key = "C. Purdy and Purdy 1990b",
	author = "C. N. Purdy and G. B. Purdy",
	title = "Networks for greatest common divisor computations",
	journal = CN,
	volume = 73,
	year = "{\noopsort{1990b}}1990",
	pages = "125-132"}

@incollection{Deng:1989,
	key = "Deng 1989",
	author = "X. Deng",
	title = "On the parallel complexity of integer programming",
	booktitle = SPAA89,
	year = 1989,
	pages = "110-116",
	publisher = ACM}

@article{Meidanis:1991,
	key = "Meidanis 1991",
	author = "J. Meidanis",
	title = "Lower bounds for arithmetic problems",
	journal = IPL,
	volume = 38,
	year = 1991,
	pages = "83-87"}

@article{Shallit&Sorenson:1994,
	key = "Shallit and Sorenson 1994",
	author = "J. O. Shallit and J. Sorenson",
	title = "Analysis of a left-shift binary {GCD} algorithm",
	journal = JSC,
	volume = 17,
	year = 1994,
	pages = "473-486"}

@article{Meijer:1992,
	key = "Meijer 1992",
	author = "A. R. Meijer",
	title = "How fast is the {Euclidean} algorithm?",
	journal = "Int. J. Math. Educ. Sci. Technol.",
	volume = 23,
	year = 1992,
	pages = "324-328"}

@article{Nievengloski:1849,
	key = "Nievengloski 1849",
	author = "G.-H. Nievengloski",
	title = "Note sur une {abr\'eviation} dans la recherche
du plus grand commun diviseur de deux nombres",
	journal = NAM,
	volume = 8,
	year = 1849,
	pages = "447-448"}

@article{Nievengloski:1845,
	key = "Nievengloski 1845",
	author = "G.-H. Nievengloski",
	title = "Sur la limite {sup\'erieure} du nombre de
divisions {\`a} faire pour trouver le plus grand commun
diviseur de deux nombres",
	journal = NAM,
	volume = 4,
	year = 1845,
	pages = "568-573"}

@article{Serret:1852,
	key = "Serret 1852",
	author = "J.-A. Serret",
	title = "{Th\'eor\`eme} {d'arithm\'etique}",
	journal = NAM,
	volume = 11,
	year = 1852,
	pages = "414-416"}

@inproceedings{Jebelean:1993a,
	key = "Jebelean 1993a",
	author = "T. Jebelean",
	title = "Comparing several {GCD} algorithms",
	booktitle = "Proc. 11th Symp. Comp. Arith.",
	editor = "Swartzlander, Jr., E. and M. J. Irwin and G. Jullien",
	publisher = IEEEPR,
	year = 1993,
	pages = "180-185"}

@inproceedings{Jebelean:1993b,
	key = "Jebelean 1993b",
	author = "T. Jebelean",
	title = "A generalization of the binary {GCD} algorithm",
	booktitle = "ISSAC '93:  Proc. 1993 Int'l. Symp. Symb. Alg. Comp.",
	editor = "M. Bronstein",
	publisher = ACM,
	year = 1993,
	pages = "111-116"}

@inproceedings{Jebelean:1993c,
	key = "Jebelean 1993c",
	author = "T. Jebelean",
	title = "Improving the multiprecision {Euclidean} algorithm",
	booktitle = DISCO93,
	editor = "A. Miola",
	year = 1993,
	series = LNICS,
	publisher = SV,
	volume = 722,
	pages = "45-58"}

@phdthesis{Ge:1993,
	key = "Ge 1993",
	author = "G. Ge",
	title = "Algorithms related to multiplicative representations of
algebraic numbers",
	school = "University of California, Berkeley",
	year = 1993}

@article{Sorenson:1994,
	key = "Sorenson 1994",
	author = "J. Sorenson",
	title = "Two fast {GCD} algorithms",
	journal = JA,
	volume = 16,
	year = 1994,
	pages = "110-144"}

@article{Buchmann&Lenstra:1994,
	key = "Buchmann and Lenstra 1994",
	author = "J. A. Buchmann and Lenstra, Jr., H. W.",
	title = "Approximating rings of integers in number fields",
	journal = JTNB,
	volume = 6,
	year = 1994,
	pages = "221-260"}

@article{Shallit:1994,
	key = "Shallit 1994",
	author = "J. O. Shallit",
	title = "Origins of the analysis of the {Euclidean} algorithm",
	journal = HM,
	volume = 21,
	year = 1994,
	pages = "401-419"}

@inproceedings{Moenck:1973,
	key = "Moenck 1973",
	author = "R. T. Moenck",
	title = "Fast computation of {GCDs}",
	booktitle = STOC73,
	publisher = ACM,
	year = 1973,
	pages = "142-151"}

@article{Plankensteiner:1970,
	key = "Plankensteiner 1970",
	author = "B. Plankensteiner",
	title = "Untersuchung {\"uber} die {Schrittanzahl} des euklidischen
{Algorithmus} bei {Andwendung} auf echte {Br\"uche}",
	journal = MMATH,
	volume = 74,
	year = 1970,
	pages = "244-257"}

@article{Kilian:1983,
	key = "Kilian 1983",
	author = "H. Kilian",
	title = "Zur mittleren {Anzahl} von {Schritten} beim euklidischen {Algorithmus}",
	journal = ELEM,
	volume = 38,
	year = 1983,
	pages = "11-15"}

@incollection{Majewski&Havas:1994,
	key = "Majewski and Havas 1994",
	author = "B. S. Majewski and G. Havas",
	title = "The complexity of greatest common divisor computations",
	booktitle = ANTS1,
	editor = "L. M. Adleman and M.-D. Huang",
	series = LNICS,
	volume = 877,
	publisher = SV,
	year = 1994,
	pages = "184-193"}

@article{WilliamsI:1976,
	key = "I. Williams 1976",
	author = "I. S. Williams",
	title = "On a problem of {Kurt Mahler} concerning binomial
coefficients",
	journal = BAUSMS,
	volume = 14,
	year = 1976,
	pages = "299-302"}

@article{Breusch:1979,
	key = "Breusch 1979",
	author = "R. Breusch",
	title = "Solution to Elementary Problem {E2686}",
	journal = AMM,
	volume = 86,
	year = 1979,
	pages = "131"}

@unpublished{Havas&Majewski&Matthews:1995,
	key = "Havas, Majewski, and Matthews 1995",
	author = "G. Havas and B. S. Majewski and K. R. Matthews",
	title = "Extended gcd algorithms",
	note = "Unpublished manuscript",
	comment = "See HMM 1998",
	year = 1995}

@article{Weber:1995,
	key = "Weber 1995",
	author = "K. Weber",
	title = "The accelerated integer {GCD} algorithm",
	journal = ACMTOMS,
	volume = 21,
	year = 1995,
	pages = "111-122"}

@article{Ficken:1943,
	key = "Ficken 1943",
	author = "F. A. Ficken",
	title = "{Rosser's} generalization of the {Euclid} algorithm",
	journal = DMJ,
	volume = 10,
	year = 1943,
	pages = "355-379"}

@article{Jebelean:1995,
	key = "Jebelean 1995",
	author = "T. Jebelean",
	title = "A double-digit {Lehmer-Euclid} algorithm for finding
the {GCD} of long integers",
	journal = JSC,
	volume = 19,
	year = 1995,
	pages = "145-157"}

@article{Havas&Majewski&Matthews:1998,
	key = "Havas, Majewski, and Matthews 1998",
	author = "G. Havas and B. S. Majewski and K. R. Matthews",
	title = "Extended gcd and {Hermite} normal form algorithms
via lattice reduction",
	journal = EXPM,
	volume = 7,
	year = 1998,
	pages = "125-136"}