高中数学选修5-3(密码学算法基础) 选修课密码学3 课件.ppt

《高中数学选修5-3(密码学算法基础) 选修课密码学3 课件.ppt》由会员分享，可在线阅读，更多相关《高中数学选修5-3(密码学算法基础) 选修课密码学3 课件.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、密码学数学引论密码学数学引论邢星邢星 xing.creature_杭州第七中学 密码学的数学引论密码学的数学引论现代密码学是以数学作为基础的每个现代密码算法，都有其数学背景，依赖某一种数学理论。数论、域论、有限域理论、计算复杂性理论。31.因子因子 设设a，b(b0)是两个整数，如果存在另一整是两个整数，如果存在另一整 数数m，使得使得a=mb，则称，则称b整除整除a，记为，记为b|a，且称，且称b是是a的的因子因子。整数具有以下性质：整数具有以下性质：a|1，那么，那么a=1。a|b且且b|a，则，则a=b。对任一对任一b(b0)，b|0。b|g，b|h，则对任意整数，则对任意整数m、n有有

2、b|(mg+nh)。1.1 素数和互素数素数和互素数1数论数论42.素数素数 称整数称整数p(p1)是是素数素数，如果，如果p的因子只有的因子只有1，p。任一整数任一整数a(a1)都能惟一地分解为以下形式：都能惟一地分解为以下形式：其中其中p1p2pt是素数，是素数，ai0(i=1,t)。例如。例如91=13 7，11011=13 112 7这一性质称为这一性质称为算术基本定理。算术基本定理。这一性质也可表示为：这一性质也可表示为：1.1 素数和互素数素数和互素数5两数相乘等价于这两个数的分解式中相同因子的指数两数相乘等价于这两个数的分解式中相同因子的指数相加相加，即由，即由k=mn 可得：可

3、得：对每一素因子对每一素因子p,kp=mp+np例如：(1)(2)由（1）和（2）式得：1.1 素数和互素数素数和互素数6若若a|b，且，且a和和b的分解式中，都有素的分解式中，都有素p的幂，则的幂，则 对对每一素数每一素数p的的幂指数幂指数ap和和bp,有有 apbp。例如：15|45，15=5X345=5X323.互素数互素数称称c是两个整数是两个整数a、b的的最大公因子最大公因子，满足，满足 c是是a的因子也是的因子也是b 的因子，即的因子，即c是是a、b的公因子。的公因子。a和和b的任一公因子，也是的任一公因子，也是c的因子。的因子。表示为表示为c=gcd(a,b)。规定c01.1 素

4、数和互素数素数和互素数如果如果gcd(a,b)=1，则称，则称a和和b互素互素。7设设n是一正整数，是一正整数，a是整数，如果用是整数，如果用n除除a，得商为，得商为q，余数为余数为r，则，则 a=qn+r,0rn,用用a mod n表示余数表示余数r如果如果(a mod n)=(b mod n)，则称两整数，则称两整数a和和b模模n同同余余，记为，记为ab mod n。称与称与a模模n同余的数的全体为同余的数的全体为a的的同余类同余类，记为，记为a，称称a为这个为这个同余类的表示元素同余类的表示元素。1.2 模运算模运算8同余有以下性质：同余有以下性质：若若n|(a-b)，则，则ab mod

5、 n。(试证明试证明)(a mod n)(b mod n)，则，则ab mod n。ab mod n,则则ba mod n。ab mod n,bc mod n,则则ac mod n。从以上性质易知，同余类中的每一元素都可作为这从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。个同余类的表示元素。1.2 模运算模运算9求余数运算（简称求余运算）求余数运算（简称求余运算）a mod n将整数将整数a映射到映射到集合集合0,1,n-1，称，称求余运算求余运算在这个集合上的算术运在这个集合上的算术运算为算为模运算模运算。例如：a模8的运算将整数a映射到0,1,2,3,4,5,6,7上。-

6、9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7-9=q*8+r 0=rq=-2,r=7-8=q*8+r 0=rq=-1,r=01.2 模运算模运算10模运算有以下性质：模运算有以下性质：(a mod n)+(b mod n)mod n=(a+b)mod n。(a mod n)-(b mod n)mod n=(a-b)mod n。(a mod n)(b mod n)mod n=(ab)mod n。例例4.1 设设Z8=0,1,7，考虑，考虑Z8上的模加法和模乘法上的模加法和模乘法.一般地，定义一般地，定义Zn为小于为小于n

7、的所有非负整数集合，即的所有非负整数集合，即Zn=0,1,n-1，称，称Zn为模为模n的的同余类集合同余类集合。其上。其上的模运算有以下性质：的模运算有以下性质：1.2 模运算模运算11 交换律交换律 (w+x)mod n=(x+w)mod n(wx)mod n=(xw)mod n 结合律结合律 (w+x)+y mod n=w+(x+y)mod n(wx)y mod n=w(xy)mod n 分配律分配律 w(x+y)mod n=wx+wy mod n 单位元单位元 (0+w)mod n=w mod n(1w)mod n=w mod n 加法逆元加法逆元 对对wZn，存在，存在zZn，使得，使得 w+z0 mod n，记，记z=-w。1.2 模运算模运算12定理1-1设设aZn，gcd(a,n)=1，则，则a在在Zn中有乘法逆元。中有乘法逆元。例如：模8的乘法运算，1，3，5，7有逆元。X012345670000000001012345672024602463036147254040404045052741636064206427076543211.2 模运算模运算试求模试求模9乘乘法运算中哪法运算中哪些元素有逆些元素有逆元，逆元是元，逆元是什么？什么？