Algorithm 2 in action: gcd(113192,763836,1066557,1785102)
This is output from print statements I inserted in sgcd() of my CALC program.
Algorithm 3 of HMM gives exactly the same output, apart from the
extra 10 zeros in the rightmost column.
sgcd(10^10)
The matrix entered is
1 0 0 0 1131920000000000
0 1 0 0 7638360000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
enter alpha=m1/n1: select m1 and n1 (normally 3 and 4) :1 1
Row 2 -> Row 2 + -7 x Row 1
1 0 0 0 1131920000000000
-7 1 0 0 -285080000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
-7 1 0 0 -285080000000000
1 0 0 0 1131920000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 4 x Row 1
-7 1 0 0 -285080000000000
-27 4 0 0 -8400000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
-27 4 0 0 -8400000000000
-7 1 0 0 -285080000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + -34 x Row 1
-27 4 0 0 -8400000000000
911 -135 0 0 520000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
911 -135 0 0 520000000000
-27 4 0 0 -8400000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 16 x Row 1
911 -135 0 0 520000000000
14549 -2156 0 0 -80000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
14549 -2156 0 0 -80000000000
911 -135 0 0 520000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 6 x Row 1
14549 -2156 0 0 -80000000000
88205 -13071 0 0 40000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
88205 -13071 0 0 40000000000
14549 -2156 0 0 -80000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 2 x Row 1
88205 -13071 0 0 40000000000
190959 -28298 0 0 0
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
190959 -28298 0 0 0
88205 -13071 0 0 40000000000
0 0 1 0 10665570000000000
0 0 0 1 17851020000000000
Row 3 -> Row 3 + -266639 x Row 2
190959 -28298 0 0 0
88205 -13071 0 0 40000000000
-23518892995 3485238369 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 2 and 3
190959 -28298 0 0 0
-23518892995 3485238369 1 0 10000000000
88205 -13071 0 0 40000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 123162 x Row 1
190959 -28298 0 0 0
-637 93 1 0 10000000000
88205 -13071 0 0 40000000000
0 0 0 1 17851020000000000
Row 3 -> Row 3 + -4 x Row 2
190959 -28298 0 0 0
-637 93 1 0 10000000000
90753 -13443 -4 0 0
0 0 0 1 17851020000000000
Swapping Rows 2 and 3
190959 -28298 0 0 0
90753 -13443 -4 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
90753 -13443 -4 0 0
190959 -28298 0 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + -2 x Row 1
90753 -13443 -4 0 0
9453 -1412 8 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
9453 -1412 8 0 0
90753 -13443 -4 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + -10 x Row 1
9453 -1412 8 0 0
-3777 677 -84 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
-3777 677 -84 0 0
9453 -1412 8 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 2 x Row 1
-3777 677 -84 0 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
1899 -58 -160 0 0
-3777 677 -84 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Row 2 -> Row 2 + 2 x Row 1
1899 -58 -160 0 0
21 561 -404 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Swapping Rows 1 and 2
21 561 -404 0 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
0 0 0 1 17851020000000000
Row 4 -> Row 4 + -1785102 x Row 3
21 561 -404 0 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
1137109974 -166014486 -1785102 1 0
Swapping Rows 3 and 4
21 561 -404 0 0
1899 -58 -160 0 0
1137109974 -166014486 -1785102 1 0
-637 93 1 0 10000000000
Row 3 -> Row 3 + -601379 x Row 2
21 561 -404 0 0
1899 -58 -160 0 0
-4908747 -131134504 94435538 1 0
-637 93 1 0 10000000000
Swapping Rows 2 and 3
21 561 -404 0 0
-4908747 -131134504 94435538 1 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Row 2 -> Row 2 + 233751 x Row 1
21 561 -404 0 0
24 -193 134 1 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Swapping Rows 1 and 2
24 -193 134 1 0
21 561 -404 0 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Row 2 -> Row 2 + 3 x Row 1
24 -193 134 1 0
93 -18 -2 3 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Swapping Rows 1 and 2
93 -18 -2 3 0
24 -193 134 1 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Row 2 -> Row 2 + -1 x Row 1
93 -18 -2 3 0
-69 -175 136 -2 0
1899 -58 -160 0 0
-637 93 1 0 10000000000
Row 3 -> Row 3 + 1 x Row 2
93 -18 -2 3 0
-69 -175 136 -2 0
1830 -233 -24 -2 0
-637 93 1 0 10000000000
Swapping Rows 2 and 3
93 -18 -2 3 0
1830 -233 -24 -2 0
-69 -175 136 -2 0
-637 93 1 0 10000000000
Row 2 -> Row 2 + -19 x Row 1
93 -18 -2 3 0
63 109 14 -59 0
-69 -175 136 -2 0
-637 93 1 0 10000000000
Row 3 -> Row 3 + 1 x Row 2
93 -18 -2 3 0
63 109 14 -59 0
-6 -66 150 -61 0
-637 93 1 0 10000000000
Row 4 -> Row 4 + 7 x Row 1
93 -18 -2 3 0
63 109 14 -59 0
-6 -66 150 -61 0
14 -33 -13 21 10000000000
The corresponding reduced basis is
93 -18 -2 3 0
63 109 14 -59 0
-6 -66 150 -61 0
14 -33 -13 21 10000000000
gcd(113192,763836,1066557,1785102)=1
14*113192+(-33)*763836+ (-13)*11066557+21*1785102=1
These are the smallest multipliers.