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

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

Ways to use gcdLLL :

gcdLLL(List)

For the programmer

The object gcdLLL is a method function with options.

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

Synopsis

Description

See also

Ways to use gcdLLL :

For the programmer