数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,1
2.2 数论
Number Theory
1、算术基本定理
2、同余关系
3、密码学基础数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,2
以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，
而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。
我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。
1、算术基本定理数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,3
Definition 1
定义 1 设 a,b,c是任意的三个整数,若满足 a=bc则称 b（ 或 c） 是 a的 因子 /factor,a是 b（ 或 c） 的 倍数
/multiple,b(或 c)能 整除 （ 也称 除尽 /divides） a。
记为 b∣ a 和 c∣ a。
特别地,若 b≠a且 b≠1,则称 b是 a的直因子 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,4
Theorem 1
定理 1,设 a,b,c 是任意三个整数,则下列各式成立
（ 1） 若 b∣ a,则下列各式成立 (b≠0)
(―b) ∣ a,b∣ (―a),(―b) ∣ (―a),∣ b∣┃∣ a∣
（ 2） 若 c∣ b且 b∣ a(c≠0,b≠0),则 c∣ a
（ 3） 若 b∣ a(b≠0),则 b∣ ac
（ 4） 若 b∣ a且 b∣ c(b≠0),则 b∣ (a± c)
（ 5） 若 a∣ b且 b∣ a(a≠0,b≠0),则 a=± b
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,5
Theorem 2,
定理 2 设 a,b是两个整数,b≠0,则恰存在两个整数 q,r使满足
a=bq+r 其中 0≤r<∣ b∣
定理 2中的等式 a=bq+r也可以用地板（下整）函数表示为
a=b?a/b?+(a-b?a/b? )
由此可知，定理 2对于实数集 R也是成立的。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,6
EXAMPLE 2
定义 2 设 d,a1,a2,…,an(n>=2)是任意整数,若有
d|a1,d| a2,…,d| an
则称 d是 a1,a2,…,an的 公因子 /common divisor。
若 d是 a1,a2,…,an的一个公因子,对 a1,a2,…,an的任一个公因子 c,存在 c?d,则称 d是 a1,a2,…,an的 最大公因子
/greatest common divisor,记为 (a1,a2,…,an )。 或 gcd
（ a1,a2,…,an ） 或 GCD （ a1,a2,…,an ）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,7
theorem 3
定理 3 设 a,b?I 且满足
a=b*q+r
这里 a?b,0?rb?,则
gcd(a,b) = gcd(b,r)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,8
Theorem 4
定理 4 任意两个整数都存在最大公因子 。
求两个整数的最大公因子的欧几里德算法
（ Euclid，也称辗转相除法）。
设 a,b是任意两个整数,a=qi b+ ri
i=0,1,2,…
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,9
Example 1
例 1：求 133 和 301 的最大公因子
k 0 1 2 3 4
qk 2 3 1 4
rk 35 28 7 0
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,10
Theorem 5
定理 5 设 a,b是正整数,则存在整数 s,t,满足
s*a + t*b = gcd（ a,b）
s*t+t*b,gcd(a,b)的 线性组合 表达 /
linear combination
例 2,求 gcd(252,198)的 线性组合 表达 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,11
Theorem 5
定理 5推论 设 a,b是整数,则存在整数 s、
t,满足
s*a + t*b = gcd（ a,b）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,12
Theorem 6
定理 6 设 a,b,c是正整数,且满足
gcd（ a,b） =1,a|bc,则
a|c
定理 6证明思路：利用定理 5和定理 1（ 3） （ 4）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,13
Definition 3
定义 3 若一个大于 1的正整数 p除了 1和 p之外没有其它正因子,则称 p是一个 质数 （ 或 素数 /prime） 。 一个既不是质数也不是 1的正整数称为 合数 /composite。
定义 4 设 b是 a的一个因子,如果 b本是质数,则称 b是 a
的一个 质因子 / prime factor 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,14
质数的存在性：
设 a是一个大于 1的整数,则 a的大于 1的最小因子必是质数 。
质数的判定,判断一个正整数是否为质数的局部比较方法。设 a是一个大于 1的正整数，只要考虑所有 <=? a的质数，若对每一个这样的质数 b都有 b不能整除 a，则 a就是质数，否则就不是质数。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,15
DEFINITION 5,
定义 5 设 a1,a2,…,an是任意整数 (n≥2)。 若有
(a1,a2,…,an)=1 或 （ a1,a2,…,an ） = -1
则称 a1,a2,…,an两两互质 /pairwise relatively prime。
特别地,若 (a1,a2 )=1 或 (a1,a2 )=-1,则称 a1与 a2互质
/relatively prime。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,16
Theorem 7
定理 7 设 p,a1,a2,…,an是整数,且 p是质数 。
如果 p| a1a2… an,则有
p| a1? p| a2?…? p| an
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,17
Theorem 8
定理 8（ 算术基本定理 ） 任意一个正整数 n(n≠1)可以唯一地表示为若干个质数的乘积 。 这里唯一的意义表示为不考虑质因子的次序 。
推论 1 任意一个整数 n(n≠0,n≠± 1)可以唯一地表示为 ± p1 p2 … pk ( k>=1 )
这里 p1,p2,…,pk是质数 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,18
推论 2 （ 质 数 分 解 定 理 ） 任 意 一 个 整 数
n(n≠0,n≠± 1)可以唯一地表示为
± p1r1 p2r2 … pkrk
这里 p1,p2,…,pk是质数,r1,r2,…,rk是正整数 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,19
Theorem 8
定理 9（ 欧几里德定理 ）
所有质数组成的集合是一个无限集 。
例 3,求整数 9892的质数标准分解式 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,20
EXAMPLE 4
例 4 金库内有 3根同样粗细的金条,分别长 135、
243和 558（ 单位英寸 ） 。 现在要把它们截成相等的小段,要求小段要最长 。 问一共可以把这些金条分成几段,每段几英寸 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,21
2、同余关系定义 1 设 m是一个正整数,对任意两个整数 a,b,若
a-b能被 m整除,则称 a与 b是 （ 模 m） 同余的,或 （ 模 m）
合同的 /congruent by modulo m,记为
a? b ( mod m)
在 m确定的情况下,简记为 a? b 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,22
Theorem 1
定理 1设 m是一个正整数,a,b∈ I，
则 a? b（ mod m)当且仅当存在一个整数 k 使
a = km + b
定理 1证明：
a? b（ mod m)? m | (a – b)
km = a - b?a = km+b
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,23
Theorem 2
定理 2 设 m是一个正整数,a,b,c,d∈ I，
若 a? b（ mod m),c? d（ mod m),
则有
（ 1） a ± c? b ± d (mod m)
（ 2） a c? b d (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,24
EXAMPLE 1
Hashing Function / 哈希函数设一个查找表 S有 n个数据元素 S={R1,R2,…,Rn}。 对于每个指定的 Ri,设 key是其关键字的值 。 则建立一个从 Ri.key到 Ri的存贮地址函数 H为
H(Ri,key)=addr(Ri)
称 H为 哈希函数 （ Hash）,函数值 H(Ri,key)称为 哈希地址 。 按该方法所建立的表称为 哈希表 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,25
Theorem 3
定理 3 设 m是一个正整数,a,b,c∈ I，
若 ac? bc（ mod m),gcd(c,m) = 1
则有
a? b (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,26
定理 3证明,因为 ac? bc（ mod m)
有 m| ac-bc 即 m| (a-b)c。
又有定义 gcd(c,m) = 1
则根据上节定理 6,得到 m| (a-b),即
a? b (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,27
DEFINITION 2
定义 2 设 m是一个正整数,对任意两个整数 a,b和变量 x,若存在
a x? b ( mod m)
则称 a与 b是 （ 模 m） 线性同余的 /linear congruent （ by
modulo m） 。
当 b = 1时,x的解称为 a （ 模 m） 的逆 /inverse of a
modulo m,记为数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,28
Theorem 4
定理 4 设 a与 m互质,m > 1,则 a 的逆存在 。
证明：因为 gcd(a,m) = 1 即存在 s,t? I
sa + tm = 1 从而 sa + tm? 1 ( mod m)
又因为 tm? 0 ( mod m),根据定理 2（ 1）
得到 sa? 1 ( mod m),s 是 a 的逆 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,29
Theorem 4
定理 4推论 设 a与 m互质且 a,m 为正整数,
m>a,则存在 b满足
ab?1（ mod m）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,30
Theorem 5
定理 5（ 中国同余定理 /孙子定理 ）
例 3,x? 2 ( mod 3)
x? 3 ( mod 5)
x? 2 ( mod 7)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,31
Example 4
例 4：计算机系统仅考虑 100以内的数的处理 。
如何对 x=123684 和 y = 413456进行相加运算？
解的思路：
取四个两两互质的 〈 100的数 99,98,97,95，
得到 x+y的同余数表达 。 再利用中国同余定理 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,32
Theorem 6
定理 6（ Fermat小定理 ) 设 p是一个质数,a与 p
互质,则有
ap-1? 1 ( mod p)
证明思路：考虑多项式 (1+1+… +1)p的展开式因子 。 ap? a ( mod p)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,33
Theorem 6
定理 6推论 设 m是 p和 q两个质数之积,a与 m互质,则有
a(p-1)(q-1)? 1 ( mod m)
证明思路：分别对 p和 q利用定理 6,再利用定理
2（ 2） 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,34
Theorem 7
RSA Decryption
(Rivest,Schamir,Adleman)
思路：利用质数分解的巨大工作量来达到安全的目标 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,35
Theorem 7
收报方 公开通讯 发报方
1.确定 p,q,a,k 0.待发,x1,x2,…,xn
2、发出 m,a,k m,a,k
3、发出 ci? xia (mod m)
i=1,2,…,n
c1,c2,…,cn
4、由 ci解出 xi：
x?cd(mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,36
Example 5
例 5,p=47和 q = 59
m=pq=2773,(p-1)(q-1)=2668,a=157,
d=17,k=2
x=3
3157?441(mod 2773)
44117?3(mod 2773)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,37
小 结
1、整数的因子、公因子,GCD
---EUCLID算法,GCD的线性组合
2、质数、质因子、两两互质 ---整数分解
3、同余关系、线性同余、中国同余定理
4、费尔玛小定理,RSA算法数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,38
进一步的思考
1、从 GCD到 LCM
(Least Common Multiple)
2,Cryptology
3、安全性应用关键：质数 m=pq的分解时间数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,39
练 习
pp.149 2（ f）
4,7,10,12、
21
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,1
2.2 数论
Number Theory
1、算术基本定理
2、同余关系
3、密码学基础数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,2
以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，
而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。
我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。
1、算术基本定理数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,3
Definition 1
定义 1 设 a,b,c是任意的三个整数,若满足 a=bc则称 b（ 或 c） 是 a的 因子 /factor,a是 b（ 或 c） 的 倍数
/multiple,b(或 c)能 整除 （ 也称 除尽 /divides） a。
记为 b∣ a 和 c∣ a。
特别地,若 b≠a且 b≠1,则称 b是 a的直因子 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,4
Theorem 1
定理 1,设 a,b,c 是任意三个整数,则下列各式成立
（ 1） 若 b∣ a,则下列各式成立 (b≠0)
(―b) ∣ a,b∣ (―a),(―b) ∣ (―a),∣ b∣┃∣ a∣
（ 2） 若 c∣ b且 b∣ a(c≠0,b≠0),则 c∣ a
（ 3） 若 b∣ a(b≠0),则 b∣ ac
（ 4） 若 b∣ a且 b∣ c(b≠0),则 b∣ (a± c)
（ 5） 若 a∣ b且 b∣ a(a≠0,b≠0),则 a=± b
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,5
Theorem 2,
定理 2 设 a,b是两个整数,b≠0,则恰存在两个整数 q,r使满足
a=bq+r 其中 0≤r<∣ b∣
定理 2中的等式 a=bq+r也可以用地板（下整）函数表示为
a=b?a/b?+(a-b?a/b? )
由此可知，定理 2对于实数集 R也是成立的。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,6
EXAMPLE 2
定义 2 设 d,a1,a2,…,an(n>=2)是任意整数,若有
d|a1,d| a2,…,d| an
则称 d是 a1,a2,…,an的 公因子 /common divisor。
若 d是 a1,a2,…,an的一个公因子,对 a1,a2,…,an的任一个公因子 c,存在 c?d,则称 d是 a1,a2,…,an的 最大公因子
/greatest common divisor,记为 (a1,a2,…,an )。 或 gcd
（ a1,a2,…,an ） 或 GCD （ a1,a2,…,an ）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,7
theorem 3
定理 3 设 a,b?I 且满足
a=b*q+r
这里 a?b,0?rb?,则
gcd(a,b) = gcd(b,r)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,8
Theorem 4
定理 4 任意两个整数都存在最大公因子 。
求两个整数的最大公因子的欧几里德算法
（ Euclid，也称辗转相除法）。
设 a,b是任意两个整数,a=qi b+ ri
i=0,1,2,…
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,9
Example 1
例 1：求 133 和 301 的最大公因子
k 0 1 2 3 4
qk 2 3 1 4
rk 35 28 7 0
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,10
Theorem 5
定理 5 设 a,b是正整数,则存在整数 s,t,满足
s*a + t*b = gcd（ a,b）
s*t+t*b,gcd(a,b)的 线性组合 表达 /
linear combination
例 2,求 gcd(252,198)的 线性组合 表达 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,11
Theorem 5
定理 5推论 设 a,b是整数,则存在整数 s、
t,满足
s*a + t*b = gcd（ a,b）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,12
Theorem 6
定理 6 设 a,b,c是正整数,且满足
gcd（ a,b） =1,a|bc,则
a|c
定理 6证明思路：利用定理 5和定理 1（ 3） （ 4）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,13
Definition 3
定义 3 若一个大于 1的正整数 p除了 1和 p之外没有其它正因子,则称 p是一个 质数 （ 或 素数 /prime） 。 一个既不是质数也不是 1的正整数称为 合数 /composite。
定义 4 设 b是 a的一个因子,如果 b本是质数,则称 b是 a
的一个 质因子 / prime factor 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,14
质数的存在性：
设 a是一个大于 1的整数,则 a的大于 1的最小因子必是质数 。
质数的判定,判断一个正整数是否为质数的局部比较方法。设 a是一个大于 1的正整数，只要考虑所有 <=? a的质数，若对每一个这样的质数 b都有 b不能整除 a，则 a就是质数，否则就不是质数。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,15
DEFINITION 5,
定义 5 设 a1,a2,…,an是任意整数 (n≥2)。 若有
(a1,a2,…,an)=1 或 （ a1,a2,…,an ） = -1
则称 a1,a2,…,an两两互质 /pairwise relatively prime。
特别地,若 (a1,a2 )=1 或 (a1,a2 )=-1,则称 a1与 a2互质
/relatively prime。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,16
Theorem 7
定理 7 设 p,a1,a2,…,an是整数,且 p是质数 。
如果 p| a1a2… an,则有
p| a1? p| a2?…? p| an
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,17
Theorem 8
定理 8（ 算术基本定理 ） 任意一个正整数 n(n≠1)可以唯一地表示为若干个质数的乘积 。 这里唯一的意义表示为不考虑质因子的次序 。
推论 1 任意一个整数 n(n≠0,n≠± 1)可以唯一地表示为 ± p1 p2 … pk ( k>=1 )
这里 p1,p2,…,pk是质数 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,18
推论 2 （ 质 数 分 解 定 理 ） 任 意 一 个 整 数
n(n≠0,n≠± 1)可以唯一地表示为
± p1r1 p2r2 … pkrk
这里 p1,p2,…,pk是质数,r1,r2,…,rk是正整数 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,19
Theorem 8
定理 9（ 欧几里德定理 ）
所有质数组成的集合是一个无限集 。
例 3,求整数 9892的质数标准分解式 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,20
EXAMPLE 4
例 4 金库内有 3根同样粗细的金条,分别长 135、
243和 558（ 单位英寸 ） 。 现在要把它们截成相等的小段,要求小段要最长 。 问一共可以把这些金条分成几段,每段几英寸 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,21
2、同余关系定义 1 设 m是一个正整数,对任意两个整数 a,b,若
a-b能被 m整除,则称 a与 b是 （ 模 m） 同余的,或 （ 模 m）
合同的 /congruent by modulo m,记为
a? b ( mod m)
在 m确定的情况下,简记为 a? b 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,22
Theorem 1
定理 1设 m是一个正整数,a,b∈ I，
则 a? b（ mod m)当且仅当存在一个整数 k 使
a = km + b
定理 1证明：
a? b（ mod m)? m | (a – b)
km = a - b?a = km+b
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,23
Theorem 2
定理 2 设 m是一个正整数,a,b,c,d∈ I，
若 a? b（ mod m),c? d（ mod m),
则有
（ 1） a ± c? b ± d (mod m)
（ 2） a c? b d (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,24
EXAMPLE 1
Hashing Function / 哈希函数设一个查找表 S有 n个数据元素 S={R1,R2,…,Rn}。 对于每个指定的 Ri,设 key是其关键字的值 。 则建立一个从 Ri.key到 Ri的存贮地址函数 H为
H(Ri,key)=addr(Ri)
称 H为 哈希函数 （ Hash）,函数值 H(Ri,key)称为 哈希地址 。 按该方法所建立的表称为 哈希表 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,25
Theorem 3
定理 3 设 m是一个正整数,a,b,c∈ I，
若 ac? bc（ mod m),gcd(c,m) = 1
则有
a? b (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,26
定理 3证明,因为 ac? bc（ mod m)
有 m| ac-bc 即 m| (a-b)c。
又有定义 gcd(c,m) = 1
则根据上节定理 6,得到 m| (a-b),即
a? b (mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,27
DEFINITION 2
定义 2 设 m是一个正整数,对任意两个整数 a,b和变量 x,若存在
a x? b ( mod m)
则称 a与 b是 （ 模 m） 线性同余的 /linear congruent （ by
modulo m） 。
当 b = 1时,x的解称为 a （ 模 m） 的逆 /inverse of a
modulo m,记为数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,28
Theorem 4
定理 4 设 a与 m互质,m > 1,则 a 的逆存在 。
证明：因为 gcd(a,m) = 1 即存在 s,t? I
sa + tm = 1 从而 sa + tm? 1 ( mod m)
又因为 tm? 0 ( mod m),根据定理 2（ 1）
得到 sa? 1 ( mod m),s 是 a 的逆 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,29
Theorem 4
定理 4推论 设 a与 m互质且 a,m 为正整数,
m>a,则存在 b满足
ab?1（ mod m）
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,30
Theorem 5
定理 5（ 中国同余定理 /孙子定理 ）
例 3,x? 2 ( mod 3)
x? 3 ( mod 5)
x? 2 ( mod 7)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,31
Example 4
例 4：计算机系统仅考虑 100以内的数的处理 。
如何对 x=123684 和 y = 413456进行相加运算？
解的思路：
取四个两两互质的 〈 100的数 99,98,97,95，
得到 x+y的同余数表达 。 再利用中国同余定理 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,32
Theorem 6
定理 6（ Fermat小定理 ) 设 p是一个质数,a与 p
互质,则有
ap-1? 1 ( mod p)
证明思路：考虑多项式 (1+1+… +1)p的展开式因子 。 ap? a ( mod p)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,33
Theorem 6
定理 6推论 设 m是 p和 q两个质数之积,a与 m互质,则有
a(p-1)(q-1)? 1 ( mod m)
证明思路：分别对 p和 q利用定理 6,再利用定理
2（ 2） 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,34
Theorem 7
RSA Decryption
(Rivest,Schamir,Adleman)
思路：利用质数分解的巨大工作量来达到安全的目标 。
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,35
Theorem 7
收报方 公开通讯 发报方
1.确定 p,q,a,k 0.待发,x1,x2,…,xn
2、发出 m,a,k m,a,k
3、发出 ci? xia (mod m)
i=1,2,…,n
c1,c2,…,cn
4、由 ci解出 xi：
x?cd(mod m)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,36
Example 5
例 5,p=47和 q = 59
m=pq=2773,(p-1)(q-1)=2668,a=157,
d=17,k=2
x=3
3157?441(mod 2773)
44117?3(mod 2773)
数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,37
小 结
1、整数的因子、公因子,GCD
---EUCLID算法,GCD的线性组合
2、质数、质因子、两两互质 ---整数分解
3、同余关系、线性同余、中国同余定理
4、费尔玛小定理,RSA算法数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,38
进一步的思考
1、从 GCD到 LCM
(Least Common Multiple)
2,Cryptology
3、安全性应用关键：质数 m=pq的分解时间数 论
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,39
练 习
pp.149 2（ f）
4,7,10,12、
21
