密码学的数学基础.pptx

密码学中的基本数学知识;数论在信息安全中的应用;3;4;1、除数(因子)的概念：

设z为由全体整数而构成的集合，若b≠0且

使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).

注:若a=mb+r且0rb,此时b不整除a,记为

2、素数(质数)的概念:

整数p1被称为素数是指p的因子仅有1,-1,p,-p。;6;7;8;9;§算术基本定理：

任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1＜P2＜P3…＜Pt是素数，其中αi0

§最大公约数：

若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是互素的。;11;(56,21)=?

56=2*21+1456≡14mod21

9≡3mod6

21=1*14+7

14=2*7+0

(56,21)=7;0，1,2,3,4,5,6,7,8,9,10,11,12,13,……;;带余除法：

?a∈z,0，可找出两个唯一确定的整数q和r,

使a=qm+r,0=rm,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则m∣a）

整数同余：

定义：如果amodm=bmodm，则称整数a模正整数m同余于整数b，并写a≡b（modm）是指m∣（a－b）,m称为模数。

注：1*.m∣a-b?a=q1m+r,b=q2m+r即a和b分别除以m有相同的余数。“同余”二字的来源就在于此。;2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：

自反性：对任意整数a有：a≡a（modm）

对称性：如果a≡b(modm)，则b≡a（modm）

传递性：如果a≡b(modm）b≡c（modm），则a≡c(modm)

于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。;3*.对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘，可结合：

(1)[a(modm)±b(modm)]modm=(a±b)(modm)

(2)[a(modm)*b(modm)]modm=a*b(modm)

(3)[(a*b)modm+(a*c)modm]=[a*(b+c)]modm

例子.通过同余式演算证明：

（1）560－1是56的倍数:560－1≡0mod56即560≡1mod56

（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（modm）来说，若gcd(a,m)＝1则b≡c(modm);例如1：附加条件不满足的情况

6×3≡6×7mod8

但3≡7mod8

例如2：附加条件满足的情况

5×3≡5×11mod8

3≡11mod8;原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。;22;23;24;扩展的欧几里德算法描述;例：求gcd(20,117)和20-1mod117;Euler定理与Fermat定理;Euler函数;例子：;欧拉定理（Euler）（文字表述）：

若整数a与整数n互素，则a?(n)≡1(modn)

注：

1*.n＝p时，有ap-1≡1(modp)为Fermat定理！

2*.易见a?(n)+1≡a(modn);§Fermat定理：如果p是素数并且a是不能被p整除的正整数,那么，ap-1≡1(modp)