# gcdLLL -- compute the gcd of integers, and small multipliers

## Synopsis

• Usage:
(g,z) = gcdLLL m
• Inputs:
• m, a list, of integers
• Optional inputs:
• Strategy (missing documentation) => ..., default value null,
• Threshold (missing documentation) => ..., default value 3/4,
• Outputs:
• g, an integer, the gcd of the integers in the list s
• z, , of integers

## Description

This function is provided by the package LLLBases.

The first n-1 columns of the matrix z form a basis of the kernel of the n integers of the list s, and the dot product of the last column of z and s is the gcd g.

The method used is described in the paper:

Havas, Majewski, Matthews, Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction, Experimental Mathematics 7:2 p. 125 (1998).

For an example,

 i1 : s = apply(5,i->372*(random 1000000)) o1 = {306370272, 229247604, 135272220, 220821804, 229345440} o1 : List i2 : (g,z) = gcdLLL s o2 = (372, | 1 -2 11 48 -20 |) | -5 -24 -2 -19 7 | | -12 15 -15 -7 7 | | 7 5 -31 0 11 | | 4 13 26 -41 5 | o2 : Sequence i3 : matrix{s} * z o3 = | 0 0 0 0 372 | 1 5 o3 : Matrix ZZ <--- ZZ