密码学数学基础ppt课件

密码学数学,1,整数性质,教学目的和要求（1）深刻理解整除、最大公因数、最小公倍数、质数的概念，正确理解带余数除法的意义及作用。（2）掌握并能直接运用辗转相除法求最大公因数。,2,第一节整除与带余数除法,定义1设a，b是整数，b0，如果存在整数q，使得a=bq成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：ba；如果不存在整数q使得a=bq成立，则称b不能整除a或a不被b整除，记作：ba。,3,第一节整除与带余数除法,定理1下面的结论成立：(1)ab，bcac；（传递性）(2)ma，mbm(ab)(3)mai，i=1,2,nma1q1a2q2anqn，此处qiZ（i=1,2,n）。,4,第一节整除与带余数除法,注：abab；babcac，此处c是任意的非零整数；ba，a0|b|a|；ba且|a|0，则存在唯一的两个整数q和r，使得a=bqr，0r1只能被1和它本身整除，则该数为素数（也叫质数）100以内的素数有25个，分别是2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89和97。,7,任何大于1的整数a都可以分解成素数幂之积，且唯一。其中，pi为素数，ai为正整数。,8,第三节最大公因数,定义1设a1,a2,an是n（n2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1,a2,an的一个公因数；其中最大的一个公因数叫做a1,a2,an的最大公因数。记为(a1,a2,an)。由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。,9,最大公因数,若(a1,a2,an)=1，则称a1,a2,an是互质的；若(ai,aj)=1，1i,jn，ij，则称a1,a2,an是两两互质的。显然，a1,a2,an两两互质可以推出(a1,a2,an)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2。,10,最大公因数,由上我们容易得到：定理（裴蜀（Bzout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，tZ，使得asbt=(a,b),11,最大公因数,推论(a,b)1的充要条件是：存在s，tZ，使得asbt=1。此题可以推广为：推论(a1,a2,an)=1的充要条件是：存在整数x1,x2,xn，使得a1x1a2x2anxn=1。,12,欧几里德公式,13,第四节模运算,令整数及，若(k为任一整数)，则称在modn下与b同余，记为性质：,，,。,14,例（7+9）mod11（79）mod11计算97mod13证明13200-1是51的倍数,15,例说明是否被641整除。解：224，2416，28256，216154，2321(mod641)。因此0(mod641)，即641,16,例求(2573346)26mod50解：(2573346)26(7334)26=7(72)164267(1)16426=(74)26326=3(35)53(7)5=37(72)22129(mod50)，即所求的余数是29。,17,第五节模逆元,模逆元的计算可以通过扩展欧几里德算法实现。,18,第六节费马欧拉定理,费马定理如果p是素数，且p不能被a整除，那么,19,欧拉函数表示比m小，且与m互素的正整数的个数欧拉函数性质：当m是素数时，=m-1当m=pq，且p、q（pq）均为素数时，=(p-1)(q-1),20,计算欧拉函数的公式1.若一个数m可以写成m=(为素数)，则2.对任一正整数m，若其可写成，则,21,欧拉定理对于任何互素的两个整数a和n，有当n为素数时，欧拉定理相当于费马定理,22,求7803的后三位数字求11803的后三位数字,23,思考1、如果今天是星期一，问从今天起再过天是星期几？,24,第七节本原元,对于任何互素的两个整数a和n，在方程中，至少有一个正整数m满足这一方程（因为是其中的一个解），那么，最小的正整数解m为模n下a的阶。如果a的阶m=，称a为n的本原元。,25,第八节中国剩余定理,孙子算经下卷第26题所提出的问题如下:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何？”“答曰：二十三。”,26,相当于求同余方程组n2(mod3)n3(mod5)n2(mod7)23,27,28,例韩信点兵:有兵一队,若列成五行纵队,则末行一人;成六行纵队,则末行五人;成七行纵队,则末行四人;成十一行纵队,则末行十人,求兵数.,29,x=2100+2310k,k=0,1,2,.,30,解设x是所求兵数,则依题意:x1(mod5),x5(mod6)，x4(mod7),x10(mod11)令m1=5,m2=6,m3=7,m4=11,b1=l,b2=5,b3=4,b4=10.,31,于是m=m1m2m3m4=56711=2310,M1=2310/5=462,M2=385,M3=330,M4=210.有M1M11(mod5),即1462M1