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