## 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

CALC; GAP; Magma
Full Text:

### References:

 [1] DOI: 10.2307/2312260 · Zbl 0116.26801 [2] Bosnia W., J. Symbolic Comput. 24 (3) pp 235– (1997) · Zbl 0898.68039 [3] Bradley G. H., Comm. ACM 13 pp 433– (1970) · Zbl 0195.47201 [4] Brentjes A. J., Multidimensional continued fraction algorithms (1981) · Zbl 0471.10024 [5] Cohen H., A course in computational algebraic number theory (1993) · Zbl 0786.11071 [6] Daberkow M., Dissertation, in: Über die Bestimmung der ganzen Elemente in Radikalerweiterungen algebraischer Zahlkörper (1995) · Zbl 0867.11088 [7] de Weger B. M. M., J. Number Theory 26 (3) pp 325– (1987) · Zbl 0625.10013 [8] Ficken F. A., Duke Math. J. 10 pp 355– (1943) · Zbl 0061.08503 [9] Ford D., Algorithmic number theory (Talence, 1996) pp 145– (1996) [10] DOI: 10.1007/978-3-642-97881-4 [11] Havas G., Congr. Numer. 105 pp 87– (1994) [12] Havas G., Congr. Numer. 111 pp 104– (1995) [13] Hoggatt V. E., Fibonacci and Lucas Numbers (1969) [14] DOI: 10.1515/crll.1868.69.1 · JFM 01.0065.01 [15] Kertzner S., Amer. Math. Monthly 88 (3) pp 200– (1981) · Zbl 0458.10014 [16] Knuth D. E., The art of computer programming, Vol. 2: Seminumerical algorithms,, 1. ed. (1969) · Zbl 0191.18001 [17] Knuth D. E., The art of computer programming, Vol. 2: Seminumerical algorithms,, 2. ed. (1981) · Zbl 0477.65002 [18] DOI: 10.1007/BF01457454 · Zbl 0488.12001 [19] Majewski B. S., Algorithmic number theory (Ithaca, NY 1994) pp 184– (1994) [20] 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 [21] Matthews K. R., Acta Arith. 75 (3) pp 205– (1996) [22] DOI: 10.1017/CBO9780511661952 [23] DOI: 10.2307/2303305 · Zbl 0061.06710 [24] Rössner C., Algorithmic number theory (Talence, 1996) pp 307– (1996) [25] Schnorr C.-P., Fundamentals of computation theory (Gosen, 1991) pp 68– (1991) [26] Sch M., GAP: Groups, algorithms, and programming (1996) [27] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.