互素和最大公约数GCD gcd(a,b)=C,即c是a和b的最大公约数,当 C是a和b的因子 2任何a和b的因子也是c的因子 两个整数a,b,如果除了1以外没有公共因子,则称它们互 素( Relatively prime 8和15互素,因为8的因子是12,4,8,而15的因子是 它们唯一的公共因子。 〉如果将整数表示为素数之积,则容易确定两个正整数的最 公因子 下列关系总是成立的 如果k=gcd(a,b),则k=min(amb,对于任意的∈P 例子: 300=22x3l×52,18=2lX32 gcd(18,300)=2x3×50=6 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 9/81mfy@ustc.edu.cn 现代密码学理论与实践 9/81  gcd(a, b)=c, 即c是a和b的最大公约数, 当 1.c是a和b的因子 2.任何a和b的因子也是c的因子  两个整数 a, b, 如果除了1以外没有公共因子, 则称它们互 素(Relatively Prime) 8和15互素, 因为8的因子是1,2,4,8, 而15的因子是 1,3,5,15, 1是它们唯一的公共因子。  如果将整数表示为素数之积, 则容易确定两个正整数的最 大公因子  下列关系总是成立的 如果k=gcd(a, b), 则 kp =min(ap , bp ), 对于任意的p∊P  例子： 300=22x31x52, 18=21x32 , gcd(18, 300)=21x31x50=6