同余( congruence) 给定整数a,b及n≠0,当且仅当ab=kn时,a与b在 模n时同余,记为a= b mod n或a=nb 例:17=57:17-7=2*5; 53=711∴53-11=6*7 a≡b当且仅当 a mod n= b mod n 如果a是整数,n是正整数,定义a除以n所得之余数为 a模n。对于任意整数a,我们总可写出: a=|a/n」×n+( a mod n) 11mod7=4; 11mod7=3 如果(amodη)=( b mod n),则称整数a和b是模n同 余,表示为a= b mod n或a=nb 073=4mod23;21≡-9mod10 choat al law kuter science technologe 都 mfy@ustc.edu.cn 现代密码学理论与实践 12/55
mfy@ustc.edu.cn 现代密码学理论与实践 12/55 给定整数a, b及n≠0, 当且仅当a-b=kn时，a与b 在 模n时同余，记为 a≡b mod n 或 a≡nb 例: 17≡57 ∵17-7=2*5; 53≡711 ∵53-11=6*7 a≡nb 当且仅当 a mod n = b mod n 如果a是整数，n是正整数，定义a除以n所得之余数为 a模n。对于任意整数a，我们总可写出： a =⌊a/n」× n + (a mod n) ◦ 11 mod 7 = 4; -11 mod 7 = 3 如果(a mod n)=(b mod n), 则称整数a和b是模n同 余，表示为 a≡b mod n 或 a≡nb ◦ 73 ≡ 4 mod 23； 21 ≡ -9 mod 10
同余的性质 如果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三 cmod n→a≡ cmod n EX:23=8mod5),因为23-8=15=5X3 11=5mod8),因为-11-5=-16=8X(-2 81=0mod27),因为81-0=81=27×3 ad Can futer Science Technolog 都 mfy@ustc.edu.cn 现代密码学理论与实践 13/55
mfy@ustc.edu.cn 现代密码学理论与实践 13/55 如果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
同余的性质 (a, op a, )mod n=[a, mod n ) op(a, mod n)] mod ms ①反身性( reflexive):a= a mod n ②对称性( symmetrIc):若a= b mod n,则b= a mod n ③传递性 (transitive): 若a= b mod n且b= c mod n,则a= cmod 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)modn 6(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)modn=( a mod n· b mod r)modn ④如果aC= bd mod n且c= d mod n,gcd(c,n)=1 则a= b mod n证明:留给学生 例:3*2=1*2mod4且2=2mod4,但3≠1mod4 Cheer 之9cd(2,4)≠1 都 mfy@ustc.edu.cn 现代密码学理论与实践 14/55
mfy@ustc.edu.cn 现代密码学理论与实践 14/55 (a1 op a2 ) mod n =[(a1 mod n )] op (a2 mod n)] mod n ①反身性(reflexive)：a=a mod n ②对称性(symmetric)：若a=b mod n，则b=a mod n ③传递性(transitive): 若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
able 4.1 Arithmetic modulo 8 +01 0 123 55670 234567 4 5 6 223456701 334567012 5670123 234 667012345 770123456 0 (a) Addition modulo 8 3 5 0 01234567 000000000 101234567 202460246 614725 404040404 5274 163 606420642 w01234567 65432 mfy@ustc. ed (b) Multiplication modulo 8 (c)Additive and multiplicative 15/55 inverses modulo 8
mfy@ustc.edu.cn 现代密码学理论与实践 15/55
加法逆元和乘法逆元 加法逆元(-W 0对每一个W∈Zn,存在一个z,使得 W+z≡0modn,则z即为加法逆元-W 乘法逆元(Wl 0对每一个W∈Z,存在一个z,使得w×z≡1modp, p为素数,W与p互素,则z即为乘法逆元W 因为w与p互素,如果用w乘以乙中的所有数模p,得到 的余数将以不同次序涵盖Z中的所有数,那么至少有 个余数的值为1。因此,在乙中的某个数与w相乘模p 的余数为1,这个数就是W的莱法逆元w 在模数不是素数时,某些但非全部整数存在一个乘法逆 元(如上页的模8运算)。如果gcd(a,n)=1,则能在zn 中找到b,使得axb≡ 1 mod n,则b即为乘法逆元a-1, 因为a与n互素。7 网 mfy@ustc.edu.cn 现代密码学理论与实践 16/55
mfy@ustc.edu.cn 现代密码学理论与实践 16/55 加法逆元(-w) ◦ 对每一个w∈Zn，存在一个z，使得 w+z≡0 mod n，则z即为加法逆元-w 乘法逆元(w-1) ◦ 对每一个w∈Zp，存在一个z，使得w×z≡1 mod p， p为素数， w与p互素，则z即为乘法逆元w-1 ◦ 因为w与p互素，如果用w乘以Zp中的所有数模p，得到 的余数将以不同次序涵盖Zp中的所有数，那么至少有一 个余数的值为1。因此，在Zp中的某个数与w相乘模p 的余数为1, 这个数就是w的乘法逆元, w-1 ◦ 在模数不是素数时，某些但非全部整数存在一个乘法逆 元（如上页的模8运算）。如果gcd(a, n)=1, 则能在Zn 中找到b，使得axb ≡1 mod n，则b即为乘法逆元a -1 , 因为a与n互素