x=lmod2 x=2 mod 3 x=3mod 5 23:31:48
23:31:48 3mod5 2mod3 1mod2 x x x
4) Euclidean算法 ■用来求最大公因子gcd(n,b),令r=n,r1=b a ro=gr+r2 U<r2<rI r1=q2r2+r30<r3<r2 arm2=qm-Irm-+rm 0<rm<rm-l rmq m m 该算法可以确定最大公因子gcd(n,b)=rm 若rm=1,则说明n,b互质 ■为了计算出b关于模n的逆,需要改进 23:31:48
23:31:48 4)Euclidean算法 用来求最大公因子gcd(n,b),令r0=n, r1=b r0=q1r1+r2 0<r2<r1 r1=q2r2+r3 0<r3<r2 ……… rm-2=qm-1rm-1+rm 0<rm<rm-1 rm=qmrm 该算法可以确定最大公因子gcd(n,b)=rm 若rm＝1，则说明n,b互质 为了计算出b关于模n的逆，需要改进