模m等价类的集合表示形式：
Z / 3 {0, 1, 2} {9, 31, 1}
{0,1, 2, {0,1, 2, , m 2, m 1} 模m等价类的集合 , m 2, m 1} 模m的代表元组成的集合
模m的完全剩余系
• 例子：
第 四 讲 同 余
第 四 讲 同 余
Z/m中的结论： m≡0 mod m x+(-x)≡0 mod m x±km≡x mod m (x+y)%m=((x%m)+(y%m))%m (xy)%m=((x%m)· (y%m))%m 4.Z/mX或ZmX
2 m
em m
思考：
作业：
1 1 1 q p pq
RSA算法的可解性和安全性分析。
计算(28)，(1234) 。
因子分解难题
4.4 RSA算法 第 四 讲 同 余
由Rivest、Shamir和Adleman开发，既能加密 又可签名，易理解和实现，因而最流行。 1.RSA算法过程 密钥的生成： (1)选择两个大素数p和q，计算： n=pq以及(n)=(p-1)×(q-1)； 例如：p=11,q=17; n=187, (n)=10×16=160
1 ( p 1)(q 1) 1 1 1 pq p q pq
(3)e,d必须与(n)互素； (4)具有形式为n=pq的整数称为Blum整数。 其中p和q都是模4同余3的素数。
4.安全性分析
第 四 讲 同 余
依赖于将整数n分解为素因子的难度。 EDI攻击标准使用的RSA算法中规定n的长度为 512至1024比特位之间，且为128的倍数。 国际数字签名标准ISO/IEC 9796中规定n的长 度为512比特位。 从安全性考虑，p与q必为足够大的素数，使n的 分解无法在多项式时间内完成。要求n至少要有 1024或者2048比特(十进制的308位或616位)。
(2)选择随机数1<e<(n),gcd(e,(n))=1，计算： d=e-1 mod (n)； 例如：e=7,则d=23
第 四 讲 同 余
(3)则公钥为(e,n)，私钥(d,n)； 例如：公钥为(7,187);私钥为(23,187) 加密m：c=me mod n 解密c：m=cd mod n
Z10X={1,3,7,9}
所以(10)=4
Z35X={1,2,3,4,6,8,9,11,12,13,16,17,18, 19,22,23,24,26,27,29,31,32,33,34 } 所以：(35)=24 那么：(10000)=？ 问题：如何求欧拉函数？
回顾整数惟一分解定理
第 四 讲 同 余
欧拉函数(n)
• 欧拉函数：
定理2：若正整数m,n，满足gcd(m,n)=1，则有： (mn)=(m)(n)
4.3 两个著名的定理
(n)是什么用？
第 四 讲 同 余
预习RSA算法
RSA基于因子分解难题？ med mod n m
1.欧拉定理 对n>1,如果gcd(x,n)=1，则有：x(n)=1 mod n 2.费马小定理 对任意的整数x和素数p，有 xp-1≡1 mod p
ZmX= {y∈Zm|gcd(y,m)=1} 即：Zm中与m互素的元素的集合。 例如：Z15X={1,2,4,7,8,11,13,14} Z11X={1,2,3,4,5,6,7,8,9,10}
模m的简化剩余系==缩系
5.定理
第 四 讲 同 余
定理1：设m,n是两个互素的正整数，如果x,y 分别遍历模m,n的完全(简化)剩余系， 则nx+my遍历模mn的完全(简化)剩余系。 举例：分别用模4和模5的完全剩余系和简化剩系 来表示模20的完全剩余系和简化剩余系。 Z4={0,1,2,3} Z4X={1,3} Z5={0,1,2,3,4} Z5X={1,2,3,4} 所以：Z20={0,4,8,12,16,5,9,13,17,21,10, 14,18,22,26,15,19,23,27,31} Z20X={9,13,17,21,19,23,27,31}
4.5 一次同余式
• 简单同余方程：
第 四 讲 同 余
第 四 讲 同 余 方 程
1.定理 设m不整除a，模m的一次同余式ax=b(mod m) 有解的充要条件是(a,m)|b。有解的解数是(a,m)， 若x0是它的一个解，则它的(a,m)个解为：
xi x0 m i (mod m), i 0,1, 2,..., (a, m) 1 (a, m) b m xi s i(mod m), i 0,1, 2,..., (a, m) 1 (a, m) (a, m)
小结：
(1) (n)是什么？
第 四 讲 同 余
(n)是欧拉函数，对正整数n，(n)是满足 以下条件的i 的个数： 1in且gcd(i,n)=1 (2)欧拉函数(n)的计算方法
n p p ... p
e1 1 e2 2
1
e 1 e 1 (n) ( p1 1) p1e 1 ( p2 1) p2 ...( pm 1) pm
第 四 讲 同 余 方 程
3.举例 (1)6x=2 (mod 9) (3)3x=15 (mod 6)
(2)3x=2 (mod 5) (4)19x=38 (mod 57)
解: (1)因为(6,9)=3不整除2，无解；
(2)因为(3,5)=1|2，有解，解为x=4 (mod 5)；
(3)因为(3,6)=3|15，有解，解为： x=-1,1,3 (mod 6)； (4)因为(19,57)=19|38，有解，观察可得解为： x=2 (mod 57) 所以同余式的所有解为： x=2+2i(mod 57) i=0,1,2,…18
3. 欧拉函数(n)的定义 对于正整数n，与其互素的小于等于n的正整数的 个数表示为(n)，称为欧拉函数。 (1)=1 也可以理解为ZnX中的元素个数。
4. 欧拉函数(n)的计算
第 四 讲 同 余
举例：计算(7)，(10)，(35) Z7X={1,2,3,4,5,6} 所以(7)=6
1.x≡y mod m x模m同余y 这种关系叫模m的同余。 等价的说法有x≡y mod m 当且仅当m|x-y。 2.同余的性质 对于固定的整数m，模m同余是一个等价关系。 自反性：对于任意的x，总有x≡x mod m； 对称性：x≡y mod m y≡x mod m； 传递性：x≡y mod m,y≡z mod mx≡z mod m。 其他性质： (1) x≡y mod m ax≡ay mod m,x±a≡y±a mod m； (2) x≡y mod m ax≡ay mod am, a>0； (3) (a· b) mod m≡(a mod m· b mod m) mod m。
RSA比较慢，一般选e为3,17,65537等等。
公钥私钥的关系： d=e-1 mod (n)； 已知e和n，要得到d，需要知道(n)，由(n)的 计算公式(n)=(p-1)×(q-1)可知需要知道n的因子 分解。当n很大时，这是一个难题。
2.举例 Bob的公钥为(7,187)，私钥为(23,187)； Alice要将保险柜密码88发送Bob。
30 (15 10 6) (5 3 2) 1
8
证明：
第 四 讲 同 余
n n n n (n) n ( ... ) ( ... ) p1 pm p1 p2 p( m1) pm ( n ...) ... p1 p2 p3
容斥原理
第 四 讲 同 余
第 四 讲 同 余
3.命题 两个整数x和x’，x=qm+r, x’=q’m+r’,0≤r,r’ ≤|m|， 则x≡x’ mod m当且仅当r≡r’ mod m。 对于固定的模数m，如果x≡x’，那么对于y有 x+y ≡ x’+y mod m xy ≡ x’y mod m
推论：同余直接继承了普通算术运算的一些性质。 分配律：x(y+z)≡xy+xz mod m 加法结合律：(x+y)+z≡x+(y+z) mod m 乘法结合律：(xy)z≡x(yz) mod m 1的性质：1· x≡x· 1≡x mod m 0的性质：0+x≡x+0≡x mod m
应用密码学
计算机科学与技术学院 田秀霞 83876668@
第四讲 同余与同余式
本章主要内容
• 1 同余及其基本性质 • 2 剩余类与剩余系 • 3 几个著名定理 • 4 RSA公钥密码体制 • 5 同余式与一次同余式 • 6 中国剩余定理
4.1 同余及其基本性质 第 四 讲 同 余
4.2剩余类与剩余系
第 四 讲 同 余
第 四 讲 同 余
Z/m或者Zm 整数模m等价类的集合 给定整数x和模数m，x模m等价类： {y∈Z: y≡x mod m} 通常记为x或x，又称为x模m的同余类或者剩余类。
例：对于模数12，有
0 12 12 2400 1 13 11 2401
1 11
2
3
4
5
6
7
8
9
10 20
12 13
14 15
16 17
18 19
21 22 23 24 25 26 27 28 29 30
30 30 30 30 30 30 30 (30) 30 ( ) ( ) 2 3 2 5 3 5 2 3 5 3 5 2
1 1 1 n(1 )(1 )...(1 ) p1 p2 pm
em e2 ( p1e1 p2 ... pm )(1
1 1 1 )(1 )...(1 ) p1 p2 pm
em 1 e2 1 ( p1 1) p1e1 1 ( p2 1) p2 ...( pm 1) pm