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, a matrix, of integers

Description

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

See also

• LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)
• LLL -- compute an LLL basis
• kernelLLL (missing documentation)
• hermite (missing documentation)