EXAMPLE: x* GcD(1970, 1066)@ 1970=1X1066+904 gca(1066,904) 1066=1X904+162 gc(904,162) 904=5X162+94 gca(162,94) 162=1X94+68 gcd(94,68) 94=1X68+26 gco(68,26) 68=2X26+16 gcd(26,16) 26=1X16+10 gc(16,10) 16=1X10+6 gcd(10,6) 10=1X6+4 gc(6,4) 6=1X4+2 gc(4,2) 4=2X2+0 gcd(2,0) GCD(1970,1066)=2 anteater Science& technologe 都 mfy@ustc.edu.cn 现代密码学理论与实践 22/55mfy@ustc.edu.cn 现代密码学理论与实践 22/55 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(2, 0) GCD(1970,1066)=2