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.