### 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