Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction

REFERENCES

• Blankinship , W. A. 1963 . “A new version of the Euclidean algorithm” . Amer. Math. Monthly , 70 : 742 – 745 . [Blankinship 1963]
   Web of Science ®Google Scholar
• Bosnia , W. , Cannon , J. and Playoust , C. 1997 . “The Magma algebra system, I: The user language” . J. Symbolic Comput. , 24 ( 3–4 ) : 235 – 265 . [Bosnia et al. 1997], See http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html
   Web of Science ®Google Scholar
• Bradley , G. H. 1970 . “Algorithm and bound for the greatest common divisor of n integers” . Comm. ACM , 13 : 433 – 436 . [Bradley 1970]
   Web of Science ®Google Scholar
• Brentjes , A. J. 1981 . Multidimensional continued fraction algorithms Amsterdam : Mathematisch Centrum. . [Brentjes 1981], Mathematical Centre Tracts 145
   Google Scholar
• Cohen , H. 1993 . A course in computational algebraic number theory Berlin : Springer. . [Cohen 1993], Graduate Texts in Mathematics 138
   Google Scholar
• Daberkow , M. 1995 . Über die Bestimmung der ganzen Elemente in Radikalerweiterungen algebraischer Zahlkörper , Dissertation Berlin : Tech. Univ. Berlin. . [Daberkow 1995]
   Google Scholar
• de Weger , B. M. M. 1987 . “Solving exponential Diophantine equations using lattice basis reduction algorithms” . J. Number Theory , 26 ( 3 ) : 325 – 367 . [de Weger 1987], Erratum in 31:1 (1989), 88–89
   Web of Science ®Google Scholar
• Ficken , F. A. 1943 . “Rosser's generalization of the Euclid algorithm” . Duke Math. J. , 10 : 355 – 379 . [Ficken 1943]
   Google Scholar
• Ford , D. and Havas , G. 1996 . “A new algorithm and refined bounds for extended GCD computation”. ” . In Algorithmic number theory (Talence, 1996) Edited by: Cohen , H. 145 – 150 . Berlin : Springer. . [Ford and Havas 1996], Lecture Notes in Comput. Sci. 1122
   Google Scholar
• Grötschel , M. , Lovász , L. and Schrijver , A. 1988 . Geometric algorithms and combinatorial optimization Berlin : Springer. . [Grötschel et al. 1988], Algorithms and Combinatorics 2
   Google Scholar
• Havas , G. and Majewski , B. S. 1994 . “Hermite normal form computation for integer matrices” . Congr. Numer. , 105 : 87 – 96 . [Havas and Majewski 1994]
   Google Scholar
• Havas , G. and Majewski , B. S. 1995 . “Extended gcd calculation” . Congr. Numer. , 111 : 104 – 114 . [Havas and Majewski 1995]
   Google Scholar
• Hoggatt , V. E. Jr. 1969 . Fibonacci and Lucas Numbers Boston : Houghton Mifflin Co. . [Hoggatt 1969]
   Google Scholar
• Jacobi , C. G. J. 1868 . “Über die Auflösung der Gleichung α1x1+α2x2+.+αnxn = f · u” . J. Reine Angew. Math. , 69 : 1 – 28 . [Jacobi 1868]
   Google Scholar
• Kertzner , S. 1981 . “The linear Diophantine equation” . Amer. Math. Monthly , 88 ( 3 ) : 200 – 203 . [Kertzner 1981]
   Web of Science ®Google Scholar
• Knuth , D. E. 1969 . The art of computer programming, Vol. 2: Seminumerical algorithms, , 1st ed. Reading , MA : Addison-Wesley. . [Knuth 1969]
   Google Scholar
• Knuth , D. E. 1981 . The art of computer programming, Vol. 2: Seminumerical algorithms, , 2nd ed. Reading , MA : Addison-Wesley. . [Knuth 1981]
   Google Scholar
• Lenstra , A. K. , Lenstra , H. W. Jr. and Lovász , L. 1982 . “Factoring polynomials with rational coefficients” . Math. Ann. , 261 ( 4 ) : 515 – 534 . [Lenstra et al. 1982]
   Web of Science ®Google Scholar
• Majewski , B. S. and Havas , G. 1994 . “The complexity of greatest common divisor computations”. ” . In Algorithmic number theory (Ithaca, NY 1994) Edited by: Adleman , L. M. and Huang , M.-D. 184 – 193 . Berlin : Springer. . [Majewski and Havas 1994], Lecture Notes in Comput. Sci. 877
   Google Scholar
• Majewski , B. S. and Havas , G. “A solution to the extended gcd problem” . ISSAC'95: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation . 1995 , Montreal . Edited by: Levelt , A. H. M. pp. 248 – 253 . New York : ACM Press. . [Majewski and Havas 1995]
   Google Scholar
• Matthews , K. R. 1996 . “Minimal multipliers for consecutive Fibonacci numbers” . Acta Arith. , 75 ( 3 ) : 205 – 218 . [Matthews 1996]
   Web of Science ®Google Scholar
• Pohst , M. and Zassenhaus , H. 1989 . Algorithmic algebraic number theory Cambridge : Cambridge University Press. . [Pohst and Zassenhaus 1989], Encyclopedia of Mathematics and its Applications 30
   Google Scholar
• Rosser , B. 1941 . “A note on the linear Diophantine equation” . Amer. Math. Monthly , 48 : 662 – 666 . [Rosser 1941]
   Google Scholar
• Rössner , C. and Seifert , J.-P. 1996 . “The complexity of approximate optima for greatest common divisor computations”. ” . In Algorithmic number theory (Talence, 1996) Edited by: Cohen , H. 307 – 322 . Berlin : Springer. . [Rössner and Seifert 1996], Lecture Notes in Comput. Sci. 1122
   Google Scholar
• Schnorr , C.-P. and Euchner , M. 1991 . “Lattice basis reduction: improved practical algorithms and solving subset sum problems”. ” . In Fundamentals of computation theory (Gosen, 1991) Edited by: Budach , L. 68 – 85 . Berlin : Springer. . [Schnorr and Euchner 1991], Lecture Notes in Comput. Sci. 529
   Google Scholar
• Sch , M. 1996 . GAP: Groups, algorithms, and programming Aachen : RWTH. . [Schönert et al. 1996], Lehrstuhl D für Mathematik, See ftp://dimacs.rutgers.edu/pub/ or http://www-gap.dcs.st-and.ac.uk/~gap
   Google Scholar
• Sims , C. C. 1994 . Computation with finitely presented groups Cambridge : Cambridge University Press. . [Sims 1994], Encyclopedia of Mathematics and its Applications 48
   Google Scholar