本 同余的性质 15 。如果nl(a-b),则a≡b mod n 证明：如果nl(a-b),则有(a-b)=kn,k为某些整数， 所以a=b+kn。 故a mod n=(b+kn)除以n的余数 =b除以n的余数 b mod n 。a≡o mod n隐含b三a mod n 。a=b mod n和b三c mod n隐含a三c mod n Ex:23=8(m0d5),因为23-8=15=5x3 -11≡5(m0d8),因为-11-5=-16=8x(-2) 81三0(m0d27),因为81-0=81=27x3 2022/10/9 现代密码学理论与实践04 12/51
2022/10/9 现代密码学理论与实践04 12/51 同余的性质 ⚫ 如果n|(a-b), 则a≡b mod n 证明: 如果n|(a-b), 则有(a-b)=kn, k为某些整数， 所以a=b+kn。 故a mod n = (b + kn)除以n的余数 = b 除以n的余数 = b mod n ⚫ a≡b mod n 隐含b≡a mod n ⚫ a≡b mod n 和b≡c mod n 隐含a≡c mod n Ex: 23≡8(mod 5)，因为23-8=15=5x3 -11≡5(mod 8)，因为-11-5=-16=8x(-2) 81≡0(mod 27)，因为81-0=81=27x3
模算术运算 ”拳K 15 (a op a2)mod n =[(a1 mod n)]op (az mod n)]mod n ①反身性：a=a mod n ②对称性：若a=b mod n,则b=a mod n ③传递性：若a=b mod n且b=c mod n,则a=c mod n ④如果a=b mod n.且c=d mod n,则 a+c=(b+d)mod n a-c=(b-d)mod n ac=(bd)mod n 5(a+b)mod n=(a mod n b mod n)mod n (a-b)mod n=(a mod n-b mod n)mod n (ab)mod n=(a mod n.b mod n)mod n ⑥如果ac=bd mod n且c=d mod n,gcd(c,n)=1, 则a=b mod n证明：留给学生 例：3*2=1*2m0d4且2=2m0d4,但3≠1m0d4, ·∵gcd(2,4)≠1 2022/10/9 现代密码学理论与实践04 13/51
2022/10/9 现代密码学理论与实践04 13/51 (a1 op a2 ) mod n =[(a1 mod n )] op (a2 mod n)] mod n ①反身性：a=a mod n ②对称性：若a=b mod n，则b=a mod n ③传递性: 若a=b mod n 且b=c mod n，则a=c mod n ④如果 a=b mod n且 c=d mod n，则 a+c=(b+d) mod n a-c=(b-d) mod n a•c=(b•d) mod n ⑤ (a+b) mod n = (a mod n + b mod n) mod n (a-b) mod n = (a mod n - b mod n) mod n (a•b) mod n = (a mod n • b mod n) mod n ⑥如果ac=bd mod n 且 c=d mod n, gcd(c,n)=1, 则 a=b mod n 证明：留给学生 例： 3*2=1*2 mod 4 且 2=2 mod 4, 但3≠1 mod 4， ∵ gcd(2,4)≠1 模算术运算
Table 4.1 Arithmetic Modulo 8 少国海秦我术才 0 1 2 3 4 5 6 7 0 0 1 2 3 4 6 1 2 3 4 5 6 7 0 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 2 4 5 6 0 3 5 5 6 > 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 0 1 2 3 4 5 6 (a)Addition modulo 8 0 1 2 3 4 5 6 7 w -1W l 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 > 1 7 2 0 2 4 6 0 2 6 2 6 3 0 3 6 1 4 3 5 4 0 4 0 4 0 4 0 4 4 4 5 0 5 2 1 4 1 3 5 3 5 6 0 6 4 2 0 6 4 2 6 2 7 0 7 6 5 4 3 2 1 7 1 7 2022/10/9 (b)Multiplication modulo 8 (c)Additive and multiplicative 14/51 inverses modulo 8
2022/10/9 现代密码学理论与实践04 14/51
加法逆元和乘法逆元 15 加法逆元(-W 对每一个W∈Z,存在一个z,使得 w+z三0modn,则z即为加法逆元-w 乘法逆元(w) 对每一个w∈Zp,存在-个z,使得wz=1modp, p为素数，w与p互素，则z即为乘法逆元w1 ● 因为w与p互素，如果用w乘以Z,中的所有数模p,得到 的余数将以不同次序涵盖Z中的所有数，那么至少有 一个余数的值为1。因此，在Z中的某个数与w相乘模p 的余数为1，这个数就是w的乘法逆元，w1 某些但非全部整数存在一个乘法逆元就将使模数不再 是素数。如果gcd(a,n)=1,则能在Zn中找到b,使得 axb三1modn,则b即为乘法逆元a1,因为a与n互素。 2022/10/9 现代密码学理论与实践04 15/51
2022/10/9 现代密码学理论与实践04 15/51 加法逆元和乘法逆元 ⚫ 加法逆元(-w) ⚫ 对每一个w∈Zn，存在一个z，使得 w+z≡0 mod n，则z即为加法逆元-w ⚫ 乘法逆元(w-1 ) ⚫ 对每一个w∈Zp，存在一个z，使得wxz≡1 mod p， p为素数， w与p互素，则z即为乘法逆元w-1 ⚫ 因为w与p互素，如果用w乘以Zp中的所有数模p，得到 的余数将以不同次序涵盖Zp中的所有数，那么至少有 一个余数的值为1。因此，在Zp中的某个数与w相乘模p 的余数为1, 这个数就是w的乘法逆元, w-1 ⚫ 某些但非全部整数存在一个乘法逆元就将使模数不再 是素数。如果gcd(a, n)=1, 则能在Zn中找到b，使得 axb ≡1 mod n，则b即为乘法逆元a -1 , 因为a与n互素
模算术的性质 15 剩余集(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}中恰有一个余数 r,使得a=ri mod n,则称{r1,r2,,rn}为模n的完全剩 余集，{0,1，.，n-1}形成模n的完全剩余集。 与同余不同之处：a=nb,当且仅当a mod n=b mod n a≡r,即a=r mod n,不是说a mod n=r 比如20=314，得20=14m0d3,r=2,但20m0d3≠14， 而是20m0d3=14m0d3 2022/10/9 现代密码学理论与实践04 16/51
2022/10/9 现代密码学理论与实践04 16/51 ⚫ 剩余集(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 模算术的性质