模运算 ☆给定任意正整数n和a,用a除以n,得到的商q和 余数满足如下关系: a=qn+r0≤r<n;q=La/n」 x表示小于等于x的最大整数 n 3n n a 012 r 例:11=1×7+4,r=4 11=(-2)×7+3,r=3 密码学导论一中国科学技术大学
二、模运算 ❖给定任意正整数n和a，用a除以n，得到的商q和 余数r满足如下关系： ▪ a=qn + r 0≤r<n; q=a/n ▪ x表示小于等于x的最大整数 ▪ 例: 11=1×7+4, r=4; -11=(-2)×7+3, r=3 n 2n 3n qn (q+1)n 0 1 2 a r 密码学导论--中国科学技术大学 11
同余( congruence) 令给定整数a,b及n≠0,当且仅当a-b=kn时,a与b是 模n同余,记为a= b mod n ■例:17≡7mod5 53三11mod7 a=b mod n当且仅当 a mod n= b mod n 令若a是整数,n是正整数,定义a除以n的余数为a模 对于任意整数a,总可写出:a=La/nxn+( a mod n) 例:11mod7=4 11mod7=3 密码学导论一中国科学技术大学
同余 (congruence) ❖给定整数a, b及n≠0, 当且仅当a-b=kn时，a与b是 模n同余，记为 a≡b mod n ▪ 例：17≡7 mod 5 53≡11 mod 7 ▪ a≡b mod n当且仅当 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 密码学导论--中国科学技术大学 12
因子 Divisors 令如果a=mb,其中a,bm为整数,则当b≠0时,称 b能整除a,b是a的一个因子,或a除以b余数为0 记为ba 例:24的正因子有1,2,3,4,6,8,12和24 ◆以下关系成立 如果a1,则a=±1 如果ab,且ba,则a=±b 任何b≠0能整除0 如果bg,且bh,则对任何整数m和n,有bmg+nh 例:714and763,则7(3×14+2×63) 令如果a=0modn,则nl 密码学导论一中国科学技术大学
因子 Divisors ❖如果a=mb, 其中 a,b,m 为整数，则当b≠0时，称 b能整除a, b是a的一个因子，或a除以b余数为0， 记为b|a ▪ 例：24的正因子有1, 2, 3, 4, 6, 8, 12和24。 ❖ 以下关系成立 ▪ 如果a|1, 则a=±1 ▪ 如果a|b，且b|a, 则a=±b ▪ 任何b≠0能整除0 ▪ 如果b|g，且b|h，则对任何整数m和n，有b|(mg+nh) • 例：7|14 and 7|63，则7|(3×14 + 2×63) ❖ 如果a≡0 mod n，则n|a 密码学导论--中国科学技术大学 13
同余的性质 ☆如果n(a-b),则 e=b mod n 证明:如果n(a-b)则有(ab)=kn,k为某些整数, 所以a=b+kn。 故 a mod n=(b+kn)modn b 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 密码学导论一中国科学技术大学
同余的性质 ❖ 如果n|(a-b), 则a≡b mod n 证明：如果n|(a-b), 则有(a-b)=kn, k为某些整数， 所以a=b+kn。 故a mod n = (b + kn) mod n = b 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 密码学导论--中国科学技术大学 14
逆元 令加法逆元(-W) 对每一个W∈zn,存在一个z,使得W+z=0modn,则 z即为加法逆元W 令乘法逆元(w-1) ,使得WXZ=1modp。Z即为乘法逆元W 若P为素数,对每个W∈Z,W与p互素,存 一个z 用W以Z中的所有数模p,余数将以不同次序涵盖Z中的所 有数,其中必有一个为1。这个数就是w的乘法逆元,W1 模数不是素数时,某些但非全部整数存在一个乘法逆 元。如果gcd(a,n)=1,则能在Z中找到b,使得a×b=1 modn。b即为乘法逆元a-1 密码学导论一中国科学技术大学 15
逆元 ❖加法逆元(-w) ▪ 对每一个w∈Zn，存在一个z，使得w+z≡0 mod n，则 z即为加法逆元-w ❖乘法逆元(w-1) ▪ 若p为素数，对每一个w∈Zp，w与p互素，存在一个z ，使得w×z≡1 mod p。z即为乘法逆元w-1 • 用w乘以Zp中的所有数模p，余数将以不同次序涵盖Zp中的所 有数，其中必有一个为1。这个数就是w的乘法逆元，w-1 ▪ 模数不是素数时，某些但非全部整数存在一个乘法逆 元。如果gcd(a, n)=1, 则能在Zn中找到b，使得a×b≡1 mod n。b即为乘法逆元a -1 密码学导论--中国科学技术大学 15