剩余集 (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/55mfy@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}