文档介绍：第四章密码学的数学引论
学习要点:
了解数论、群论、有限域理论的基本概念
了解模运算的基本方法
了解欧几里德算法、费马定理、欧拉定理、中国剩余定理
了解群的性质
了解有限域中的计算方法
1、除数(因子)的概念: 设z为由全体整数而构成的集合,若 b≠0且 使得a=mb,∣a,还称b为a的除数(因子).
注:若a=mb+r且0<r<b,此时b不整除a,记为
2、素数(质数)的概念: 整数p>1被称为素数是指p的因子仅有1,-1,p,-p。
§4-1 数论
§算术基本定理:
任何一个不等于0的正整数a都可以写成唯一的表达式a=P1α1P2α2…Ptαt,这里P1<P2<P3…<Pt是素数,其中αi>0
§最大公约数:
若a,b,c∈z,如果c∣a,c∣b,称c是a和b的公约数。正
整数d称为a和b的最大公约数,如果它满足
d是a和b的公约数。
对a和b的任何一个公约数c有c∣d。
注:1*. 等价的定义形式是:
gcd(a,b)=max{k∣ k∣a且k∣b}
2*.若gcd(a,b)=1,称a与b是互素的。
带余除法: a∈z,>0,可找出两个唯一确定的整数q和r, 使a=qm+r, 0<=r< m,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则m∣a)
整数同余:
定义:如果a mod m =b mod m,则称整数a模正整数m同余于整数b,并写a≡b(mod m)是指m∣(a-b), m称为模数。 注:1*.m∣a-ba=q1m+r,b=q2m+r即a和b分别除以m有相同的余数。“同余”二字的来源就在于此。
二、模算术
2*.相对于某个固定模数m的同余关系,是整数间的一种等价关系。具有等价关系的三点基本性质:
自反性:对任意整数a有:a≡a(mod m)
对称性:如果a≡b(mod m),则b≡a(mod m)
传递性:如果a≡b (mod m)b≡c(mod m),则a≡c(mod m)
于是,全体整数集合z可按模m(m>1)分成一些两两不交的等价类。
3*. 对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘,可结合:
(1)[a(mod m)±b(mod m)]mod m=(a±b)(mod m)
(2)[a(mod m)*b(mod m)]mod m=a*b(mod m)
(3)[(a*b)modm+(a*c)modm]=[a*(b+c)]modm
:
(1)560-1是56的倍数
(2)223-1是47的倍数。
解:
注意53=125≡13(mod56)
于是有56≡169≡1(mod56)
对同余式的两边同时升到10次幂,
即有56∣560-1。
同理, 注意到26=64≡17(mod47), 于是
223=(26)3·25=(26 · 26)26 · 25
≡289*(17)*(32) mod47
≡7*17*32 (mod47)
≡ 25*32(mod47)
≡1(mod47)
于是有 47∣223-1
定理:(消去律)对于ab≡ac(mod m)来说,若gcd(a,m)=1则b≡c(mod m)
例如1:附加条件不满足的情况
6×3=18≡2mod8
6×7=42≡2mod8
但3≡7mod8
例如2:附加条件满足的情况 5×3=15≡7mod8
5×11=55≡7mod8
3≡11mod8
原因:模m的乘法运算返回的结果是0到m-1之间的数,如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。
Z8
0
1
2
3
4
5
6
7
乘以6
0
6
12
18
24
30
36
42
模8后的余数
0
6
4
2
0
6
4
2
Z8
0
1
2
3
4
5
6
7
乘以5
0
5
10
15
20
25
30
35
模8后的余数
0
5
2
7
4
1
6
3