## Extended GCD and Hermite normal form algorithms via lattice basis reduction.(English)Zbl 0922.11112

The extended gcd problem is to find, given integers $$s_1,\ldots,s_m$$, an integer multiplier vector $$x=(x_1,\ldots,x_m)$$ of small Euclidean length such that $$x_1 s_1 + \cdots + x_m s_m = \gcd(s_1,\ldots,s_m)$$. The paper proposes an algorithm based on LLL lattice basis reduction [A. K. Lenstra, H. W. Lenstra jun. and L. Lovász, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)]. The algorithm does not always produce the shortest multiplier, even when $$m=3$$. However, for $$m=3$$ the algorithm can be modified to a practical polynomial algorithm for finding an optimal solution. Generally, the solution $$x$$ produced satisfies $| x| ^2 \leq 1 + \tfrac 14(m-1)y^{m-2}| s| ^2$ where $$y\geq 4/3$$. The method is generalized to the problem of producing small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.

### MSC:

 11Y16 Number-theoretic algorithms; complexity 11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors 11C20 Matrices, determinants in number theory

Zbl 0488.12001

Magma; CALC; GAP
Full Text:

### References:

  DOI: 10.2307/2312260 · Zbl 0116.26801  Bosnia W., J. Symbolic Comput. 24 (3) pp 235– (1997) · Zbl 0898.68039  Bradley G. H., Comm. ACM 13 pp 433– (1970) · Zbl 0195.47201  Brentjes A. J., Multidimensional continued fraction algorithms (1981) · Zbl 0471.10024  Cohen H., A course in computational algebraic number theory (1993) · Zbl 0786.11071  Daberkow M., Dissertation, in: Über die Bestimmung der ganzen Elemente in Radikalerweiterungen algebraischer Zahlkörper (1995) · Zbl 0867.11088  de Weger B. M. M., J. Number Theory 26 (3) pp 325– (1987) · Zbl 0625.10013  Ficken F. A., Duke Math. J. 10 pp 355– (1943) · Zbl 0061.08503  Ford D., Algorithmic number theory (Talence, 1996) pp 145– (1996)  DOI: 10.1007/978-3-642-97881-4  Havas G., Congr. Numer. 105 pp 87– (1994)  Havas G., Congr. Numer. 111 pp 104– (1995)  Hoggatt V. E., Fibonacci and Lucas Numbers (1969)  DOI: 10.1515/crll.1868.69.1 · JFM 01.0065.01  Kertzner S., Amer. Math. Monthly 88 (3) pp 200– (1981) · Zbl 0458.10014  Knuth D. E., The art of computer programming, Vol. 2: Seminumerical algorithms,, 1. ed. (1969) · Zbl 0191.18001  Knuth D. E., The art of computer programming, Vol. 2: Seminumerical algorithms,, 2. ed. (1981) · Zbl 0477.65002  DOI: 10.1007/BF01457454 · Zbl 0488.12001  Majewski B. S., Algorithmic number theory (Ithaca, NY 1994) pp 184– (1994)  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] · Zbl 0944.11040  Matthews K. R., Acta Arith. 75 (3) pp 205– (1996)  DOI: 10.1017/CBO9780511661952  DOI: 10.2307/2303305 · Zbl 0061.06710  Rössner C., Algorithmic number theory (Talence, 1996) pp 307– (1996)  Schnorr C.-P., Fundamentals of computation theory (Gosen, 1991) pp 68– (1991)  Sch M., GAP: Groups, algorithms, and programming (1996)  DOI: 10.1017/CBO9780511574702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.