剩余集 剩余集( Set of residues 定义比n小的非负整数集合为z {0,1 n b是 a mod n的剩余,如果a= b mod n或 a是 b mod n的剩余,如果b= a mod n (1)模n的完全剩余集 Complete set of residues mod 如果对每个整数a,在集合{r1,「2,…,rn中恰有一个余 数r1,使得a=r;modn 则称1,r2,,rn为模n的完 全剩余集,{0,1,…,n-1形成模n的完全剩余集 与同余不同之处:a≡nb,当且仅当 a mod n=bmod a≡n,即a= r mod n,不是说 a mod n=r 比如20≡314,得20=14mod3,r=2,但20mod 3≠14,而是20mod3=14mod3 都 mfy@ustc.edu.cn 现代密码学理论与实践 17/55
mfy@ustc.edu.cn 现代密码学理论与实践 17/55 剩余集(Set of Residues) 定义比n小的非负整数集合为Zn： Zn ={0,1,…,(n-1)} b是a mod n 的剩余，如果 a=b mod n 或 a是b mod n的剩余，如果 b=a mod n (1)模n的完全剩余集 Complete Set of Residues mod n 如果对每个整数a，在集合{r1 ,r2 ,…,rn }中恰有一个余 数ri ,使得 a=ri mod n ,则称{r1 ,r2 ,…,rn }为模n的完 全剩余集，{0,1,…,n-1}形成模n 的完全剩余集。 与同余不同之处：a≡nb,当且仅当 a mod n=b mod n a≡n r，即a=r mod n, 不是说 a mod n = r 比如 20≡314，得20=14 mod 3, r=2，但20 mod 3 ≠14，而是20 mod 3=14 mod 3
剩余集 (2)模n的缩剩余集( Reduced set of residues mod r) 完全剩余集的一个子集,包含其中所有与n互素的元素。(小于n且与 n互素的所有非负整数构成的集合) 例:n=10,模n的完全剩余集是{0,1,2,,9},缩剩余集是{1,3,7,9} Table 4.2 Properties of Modular Arithmetic for Integers in Z Property Xpression (+r) mod n=(r+ w) mod n Commutative laws (×x)modn=(x×w)modn [(w+x)+yod n-o+(x+y)modn Associative laws 【ax)×y] modn-[x(xy)]modn [v×(x+y)]modn-[w×x)+(w×y)]modn Distributive laws +(xx y)mod n=[w+x)x(w+y)mod n (0 + w)mod n=w mod n Identities (1×w)modn= w mod n Additive inverse (w) For each wE Z. there exists a z such that w+z=0 mod n aSTe mfy@ustc.edu.cn 现代密码学理论与实践 18/55
mfy@ustc.edu.cn 现代密码学理论与实践 18/55 (2)模n的缩剩余集(Reduced set of Residues mod n) 完全剩余集的一个子集，包含其中所有与n互素的元素。（小于n且与 n互素的所有非负整数构成的集合） 例:n=10，模n的完全剩余集是{0, 1, 2,…,9}，缩剩余集是 {1, 3, 7, 9}
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/55
mfy@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