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]*||2=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