LLL extended GCD algorithm: gcd(4,6,9)

alpha = 1

Row 2 -> Row 2 - Row 1        Swapping Rows 1 and 2 
 1 0 0 4                      -1 1 0 2  
-1 1 0 2                       1 0 0 4  
 0 0 1 9                       0 0 1 9  
  
Row 2 -> Row 2 - 2 x Row 1    Swapping Rows 1 and 2 
-1  1 0 2                      3 -2 0 0  
 3 -2 0 0                     -1  1 0 2  
 0  0 1 9                      0  0 1 9  
   
Row 3 -> Row 3 - 4 x Row 2    Swapping Rows 2 and 3 
 3 -2 0 0                      3 -2 0 0  
-1  1 0 2                      4 -4 1 1  
 4 -4 1 1                     -1  1 0 2  
   
Row 2 -> Row 2 - 2 x Row 1    Row 3 -> Row 3 - 2 x Row 2 
 3 -2 0 0                      3 -2  0 0  
-2  0 1 1                     -2  0  1 1  
-1  1 0 2                      3  1 -2 0  
   
Swapping Rows 2 and 3         Row 2 -> Row 2 - Row 1 
 3 -2  0 0                     3 -2  0 0  
 3  1 -2 0                     0  3 -2 0  
-2  0  1 1                    -2  0  1 1  
 
gcd(4,6,9) = 1; multipliers found by LLL are (-2,0,1)

The shortest multiplier is  b[3]+b[1]+b[2] = (1,1,-1).

If we instead calculate gcd(9,6,4), our LLL method
gives the shortest multiplier!

Back to LLLGCD examples page