4.3欧几里得算法 uclid Algorith 数论的一个最基本的技巧 Algorithm gcd(a, n) Euclid算法,求两个正整 begin 数的最大公约数gcd(a,n, g0:=n,g1:=a, greatest common divisor Wheg;≠0do 对于任何非负的整数a和n, begin gcd(a, n)=gcd(n mod a, a gi+1=gi-1 mod g 原理是计算g1=91-mod 1:=l+ g1直到g1=0为止。 end n gcd: =gi-1 若b=gcd(a,n),则ba且bn, end →b(n-Ln/a」a)且ba→ b( n mod a)且ba} 例如:gcd(22,55)=gcd(55mod 22,22)=gcd(11,22)=11 都 mfy@ustc.edu.cn 现代密码学理论与实践 19/55mfy@ustc.edu.cn 现代密码学理论与实践 19/55 数论的一个最基本的技巧 是Euclid算法，求两个正整 数的最大公约数 gcd(a, n), greatest common divisor 对于任何非负的整数a和n， gcd(a, n)=gcd(n mod a, a) 原理是计算gi+1=gi-1 mod gi 直到 gi=0为止。 {若b=gcd(a,n),则b|a且b|n, →b|(n- ⌊n/a」a)且b|a → b|(n mod a )且 b|a } Algorithm gcd(a, n) begin g0 :=n, g1 :=a, i:=1 while gi≠0 do begin gi+1=gi-1 mod gi i:=i++ end n gcd:= gi-1 end 例如：gcd(22, 55)=gcd(55 mod 22, 22)=gcd(11, 22)=11