模算术的性质 海K专 1050 (2)模n的缩剩余集(Reduced set of Residues mod n) 完全剩余集的一个子集，指的是集合中的元素都和互素 例n=10,模n的完全剩余集是{0,1,2，.，9}，缩剩余集是{1,3,7,9} Table 4.2 Properties of Modular Arithmetic for Integers in Z Property Expression (w+x)mod n=(x+w)mod n Commutative laws (w×x)modn=(c×w)modn (w+x)+y mod n=w+(x+y)modn Associative laws [(wxx)xy]modn-[x(xy)modn w×(x+y]modn=[(w×x)+(w×y]modn Distributive laws [w+(c×y]modn=[w+x)x(w+y月]modn (0+w)mod n w mod n Identities (1×w)modn=w mod n Additive inverse (-w) For each weZ,there exists a z such that w+z=0 mod n 2022/10/9 现代密码学理论与实践04 17/51
2022/10/9 现代密码学理论与实践04 17/51 模算术的性质 (2)模n的缩剩余集(Reduced set of Residues mod n) 完全剩余集的一个子集，指的是集合中的元素都和n互素 例:n=10，模n的完全剩余集是{0, 1, 2,…,9}，缩剩余集是 {1, 3, 7, 9}
4.3欧几里得算法Euclid Algorithm 数论的一个最基本的技巧是Euclid:算法，求两个正整数 的最大公约数gcd(a,n),greatest common divisor 对于任何非负的整数a和n,gcd(a,n)=gcd(n mod a,a) 原理是计算g+=g-1modg:直到g=0为止。 Algorithm gcd(a,n) begin 90=n,g1=a,i:=1 while gi#0 do begin gi+1-gi-1 mod gi i:=i+1 end n gcd:=gi-1 end 例如：gcd(22,55)=gcd(55mod22,22)=gcd(11,22)=11 2022/10/9 现代密码学理论与实践04 18/51
2022/10/9 现代密码学理论与实践04 18/51 ⚫ 数论的一个最基本的技巧是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为止。 Algorithm gcd(a, n) begin g0 :=n, g1 :=a, i:=1 while gi≠0 do begin gi+1=gi-1 mod gi i:=i+1 end n gcd:= gi-1 end 例如：gcd(22, 55)=gcd(55 mod 22, 22)=gcd(11, 22)=11 4.3 欧几里得算法Euclid Algorithm