LLLGCD algorithm: gcd of 5 integers

gcd(2,5,14,23,29)
alpha = 1
The unimodular matrix found is

 0  1 -2  1  0
 2 -1 -1  1  0
-1  2 -1 -1  1
 2 -1 -2  0  1
 1  1  0  1 -1
Call the rows b[1],..,b[5]. Then b[5] is a multiplier
length squared = 4.

The shortest multiplier is 
b[5]-2b[1]+b[2]+b[3]+b[4]=[0,-1,0,-1,1].

The Gram-Schmidt coefficients are 

mu[21]=1/3,      mu[31]=1/2,     mu[41]=1/2,   mu[51]=1/3;
mu[32]=-6/38,    mu[42]=-12/38,  mu[52]=-16/38;
mu[43]=-107/241, mu[53]=-92/241;
mu[54]=-703/1595.

D[0]=1,D[1]=6,D[2]=38,D[3]=241,D[4]=1595,D[5]=1.

Here ||b[i]^*||²=D[i]/D[i-1].
This example is the only one where the coefficient of
b[1] in the shortest vector is not -1,1 or 0 for a  
test range of integers with gcd = 1 and lying in [2,30].


Two other randomly found examples: 

gcd(103,500,1005,204,60)

The unimodular matrix is
	 3  0 -1  4 -2
	 4 -2  0  2  3
	 4  1  0 -3 -5
	-2 -5  2  4 -2
	 1 -3  2 -3  0

b[5]=[1,-3,2,-3,0] is a multiplier of lengthsquared 23.

The Gram-Schmidt coefficients are 

mu[21]=14/30,      mu[31]=1/3,     mu[41]=2/5,   mu[51]=-11/30;
mu[32]=-350/794,    mu[42]=-48/794,  mu[52]=274/794;
mu[43]=-15646/33764, mu[53]=14048/33764;
mu[54]=612844/1315850.

D[0]=1, D[1]=30, D[2]=794, D[3]=3764, D[4]=1315850, D[5]=1.

Here the shortest is b[5]+2b[1]-b[2]-b[3]-b[4]=[1,3,-2,2,0].
lengthsquared = 18.


gcd(203,32,44,26,195)

The Gram-Schmidt coefficients are 

mu[21]=-3/7,       mu[31]=3/7,     mu[41]=-2/7,   mu[51]=-3/7;
mu[32]=44/89,      mu[42]=8/89,    mu[52]=-44/89;
mu[43]=916/1834,   mu[53]=747/1834;
mu[54]=-41236/82870.

D[0]=1,D[1]=7,D[2]=89,D[3]=1834,D[4]=82870,D[5]=1.

The unimodular matrix is

	-1  0 -1  2  1
	 0  3 -1 -2  0
	 2  2 -3  2 -2
	 1  4  4  3 -3
	 2 -3 -2 -1 -1
b[5]=[2,-3,-2,-1,-1] is a multiplier of lengthsquared 19.
The shortest multiplier is 
[-1,2,2,2,0]=b[5]+2b[1]+b[2]-b[3]+b[4]  lengthsquared 13.
The multipliers of length-squared not exceeding 19 are

   [-1,2,2,2,0]=b[5] + 2b[1]+b[2]-b[3]+b[4]  (13) 
   [0,2,3,0,-1]=b[5] +  b[1]+b[2]-b[3]+b[4]  (14) 
  [1,0,-4,-1,0]=b[5] +  b[1]+b[2]            (18) 
[-1,-2,-1,-3,2]=b[5]                         (19)
[2,-3,-2,-1,-1]=b[5] +  b[1]+b[2]-b[3]       (19)
Back to LLLGCD examples page
Last modified 4th September 2011