LLL based extended GCD algorithm in action:

gcd of 30, 40, 50, 60 integers

alpha=1, 30 integers:
324234553
7856756
3524634
5675646857
24364565
8957897589789789
464564564565
67857965897897890
4364564565
6787867867
43643564356
67867867968
546345756
324524545
678678967967
3425462668
76867896796
43264576568678
246456758678768
2464564756746
5367567568769898798
4564564262462456
578578678679689689678
263464357567568578
456437567586798679689685
456426245624564
567567567567
462564564786
87878678678
4363645635758
lllgcd finds the short multiplier
b[30] =2 0 1 0 2 0 0 0 -1 1 -1 1 0 2 0 -1\
2 0 0 -1 0 0 0 0 0 0 -3 -1 1 1
LENGTHSQUARED = 35
Fincke-Pohst finds a shortest multiplier
b[30]-b[2]+3b[3]-2b[4]+b[5]-b[6]+b[7]-b[8]+b[9]-b[10]+\
+2b[12]+2b[13]-b[15]+b[16]-b[17]+b[18]-b[19]
=0 -1 1 0 -2 0 1 0 1 0 2 0 0 1 -2 1 -3 0 0 2 0 0 0 0 0 0 0 1 0 -1
LENGTHSQUARED = 33
 alpha=1, 40 integers:
324234553
7856756
3524634
5675646857
24364565
8957897589789789
464564564565
67857965897897890
4364564565
6787867867
43643564356
67867867968
546345756
324524545
678678967967
3425462668
76867896796
43264576568678
246456758678768
2464564756746
5367567568769898798
4564564262462456
578578678679689689678
263464357567568578
456437567586798679689685
456426245624564
567567567567
462564564786
87878678678
4363645635758
67867865786
456435656
678657865857
789897689784
343643564565
678678657879
678
678678678678
6345736756756867
6575675678
lllgcd found a short multiplier b[40]:
=-1 -2 1 -1 -1 0 0 0 2 -1 0 0 -2 -1 -1 0 -1\
0 0 -1 0 0 0 0 0 0 -1 -1 -2 1 1 0 0 0 0 0 -1 0 0 0
LENGTHSQUARED=30
Fincke-Pohst found a shortest multiplier
b[40]-2b[2]-b[3]-2b[5]-b[6]+b[8]-b[12]+b[15]+\
b[16]-b[17]+b[18]-b[21]+b[23]+b[24]
=-1 1 0 1 0 0 -1 0 0 1 0 0 0 0 0 0 -1 0 0 0\
0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 -1 -1 -1 0 1
LENGTHSQUARED = 14
There is another one:
b[40]-2b[3]-b[4]+2b[5]+2b[6]-b[7]+b[8]-b[9]-b[10]\
-b[11]+b[12]+b[13]+2b[15]+2b[16]+b[17]+b[19]+b[20]\
+b[22]-b[23]-b[24]-b[25]-b[28]
=0 0 0 0 1 0 1 0 0 0 0 1 0 -1 -1 0 0 0 0 1 0\
0 0 0 0 0 -1 0 0 0 1 1 -1 -1 -1 0 1 0 0 -1
 alpha=1, 50 integers
324234553
7856756
3524634
5675646857
24364565
8957897589789789
464564564565
67857965897897890
4364564565
6787867867
43643564356
67867867968
546345756
324524545
678678967967
3425462668
76867896796
43264576568678
246456758678768
2464564756746
5367567568769898798
4564564262462456
578578678679689689678
263464357567568578
456437567586798679689685
456426245624564
567567567567
462564564786
87878678678
4363645635758
67867865786
456435656
678657865857
789897689784
343643564565
678678657879
678
678678678678
6345736756756867
6575675678
6978978978
47336575675687
67895978978978
34567456734673568758678
567548678969870798098
5786786898707980
56756754745786978
679078908790879069
5468758679689078
67548679798
lllgcd finds the short multiplier b[50]=
0 1 1 0 0 0 1 0 -1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0\
1 -1 -1 0 -1 1 0 -1 0 -1 1 0 0 1 0 0 0 0 0 0 0 0 0
LENGTHSQUARED = 16
Fincke-Pohst finds a shortest multiplier
b[50]-b[1]+6b[2]-2b[3]+5b[4]+b[5]+\
+4b[6]+3b[7]+2b[8]+2b[9]+2b[10]+b[11]-b[14]+b[20]-b[21]+\
+2b[22]+b[28]+b[29]
= -1 1 0 1 0 0 -1 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0\
0 0 0 0 1 0 1 1 1 -1 -1 -1 0 1 0 0 0 0 0 0 0 0 0 0
LENGTHSQUARED = 14
 alpha=1, 60 integers
324234553
7856756
3524634
5675646857
24364565
8957897589789789
464564564565
67857965897897890
4364564565
6787867867
43643564356
67867867968
546345756
324524545
678678967967
3425462668
76867896796
43264576568678
246456758678768
2464564756746
5367567568769898798
4564564262462456
578578678679689689678
263464357567568578
456437567586798679689685
456426245624564
567567567567
462564564786
87878678678
4363645635758
67867865786
456435656
678657865857
789897689784
343643564565
678678657879
678
678678678678
6345736756756867
6575675678
6978978978
47336575675687
67895978978978
34567456734673568758678
567548678969870798098
5786786898707980
56756754745786978
679078908790879069
5468758679689078
67548679798
4654756555878787
875765564545768686
3543434434344
8765453432
8764434555578
54434667
54332354556866
766534467756
98776754434
654534464575756
lllgcd finds the short multiplier b[60]
=-1 -1 1 1 -1 0 0 0 0 0 -1 1 0 -1 0 0 0 0 0 0 0\
0 0 0 0 0 -1 1 0 0 1 2 -1 0 0 1 0 0 0 0 1 0 0 0\
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
LENGTHSQUARED = 18
Magma finds a shortest multiplier
b[60]-2b[1]+b[2]-2b[3]-b[5]-b[6]-b[7]-b[8]-2b[9]+b[11]\
-b[14]-b[15]-b[16]+b[18]-b[19]-2b[22]+b[23]-b[24]-b[26]-b[31]
= 0 0 0 0 -1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0\
0 0 0 0 0 0 0 -1 0 -1 0 -2 0 0 0 1 0 0 0 0 0 0\
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
LENGTHSQUARED = 12
(calc's crude Fincke-Pohst seems to take forever and has not verified this.)

Back to LLLGCD examples page