EUCLID'S GCD ALGORITHM@ Euclid's algorithm to compute GCD(a, b) A←a,B←b 2.若B=0,则返回A=gcd(a,b) 3.R=A mod B A←B,B←R 转到2 Int gcd(int x, int y) Return(y)? X: gcd(y, x%y) 如果a和b只有唯一的正公因子1,则称整数a和b 是互素的,即gcd(a,b)=1 都 mfy@ustc.edu.cn 现代密码学理论与实践 20/55mfy@ustc.edu.cn 现代密码学理论与实践 20/55  Euclid's Algorithm to compute GCD(a,b): 1. A ￩ a, B ￩ b 2. 若 B=0，则返回 A=gcd(a, b) 3. R = A mod B 4. A ￩ B, B ￩ R 5. 转到2  Int gcd(int x,int y){ Return (!y) ? x: gcd(y,x%y); }  如果a和b只有唯一的正公因子1，则称整数a和b 是互素的，即gcd(a, b)=1