EUCLID'S GCD ALGORITHM(O) the greatest common divisor of a and b b=aq1+1, d=n1q2+r2, r=2q3+r3, r2=r3q4+r4, In-2=rn-1qn+In n 1n+1+0 都 mfy@ustc.edu.cn 现代密码学理论与实践 21/55mfy@ustc.edu.cn 现代密码学理论与实践 21/55 the greatest common divisor of a and b--rn