密码学数学基础.ppt

《密码学数学基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、密码学数学整数性质教学目的和要求（1）深刻理解整除、最大公因数、最小公倍数、质数的概念，正确理解带余数除法的意义及作用。（2）掌握并能直接运用辗转相除法求最大公因数。第一节整除与带余数除法定义1设a，b是整数，b0，如果存在整数q，使得a=bq成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：ba；如果不存在整数q使得a=bq成立，则称b不能整除a或a不被b整除，记作：ba。第一节整除与带余数除法定理1下面的结论成立：(1)ab，bcac；（传递性）(2)ma，mbm(a±b)(3)mai，i=1,2,,nma1q1a

2、2q2anqn，此处qi∈Z（i=1,2,,n）。第一节整除与带余数除法注：①abab；②babcac，此处c是任意的非零整数；③ba，a0

3、b

4、

5、a

6、；ba且

7、a

8、<

9、b

10、a=0。第一节整除与带余数除法定理2(带余数除法)设a与b是两个整数，b>0，则存在唯一的两个整数q和r，使得a=bqr，0r1只能被1和它本身整除，则该数为素数（也叫质数）100以内的素数有25个，分别是2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、

11、71、73、79、83、89和97。任何大于1的整数a都可以分解成素数幂之积，且唯一。其中，pi为素数，ai为正整数。第三节最大公因数定义1设a1,a2,,an是n（n≥2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1,a2,,an的一个公因数；其中最大的一个公因数叫做a1,a2,,an的最大公因数。记为(a1,a2,,an)。由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。最大公因数若(a1,a2,,an)=1，则称a1,a2,,an是互质的；若(ai,aj)=1，1i,jn，ij，则称a1,a2,,an是两两互质的。显然，a1

12、,a2,,an两两互质可以推出(a1,a2,,an)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2。最大公因数由上我们容易得到：定理（裴蜀（Bézout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，t∈Z，使得asbt=(a,b)最大公因数推论(a,b)＝1的充要条件是：存在s，t∈Z，使得asbt=1。此题可以推广为：推论(a1,a2,,an)=1的充要条件是：存在整数x1,x2,,xn，使得a1x1a2x2anxn=1。欧几里德公式第四节模运算令整数及，若(k为任一整数)，则称在modn下与b同余，记为性质：，。例（7+

13、9）mod11（7×9）mod11计算97mod13证明13200-1是51的倍数例说明是否被641整除。解：224，2416，28256，216154，2321(mod641)。因此0(mod641)，即641例求(2573346)26mod50解：(2573346)26(7334)26=[7(72)164]26[7(1)164]26=(74)26326=3(35)53(7)5=37(72)22129(mod50)，即所求的余数是29。第五节模逆元模逆元的计算可以通过扩展欧几里德算法实现。第六节费马欧拉定理费马定理如果p是素

14、数，且p不能被a整除，那么欧拉函数表示比m小，且与m互素的正整数的个数欧拉函数性质：当m是素数时，=m-1当m=pq，且p、q（p≠q）均为素数时，==(p-1)(q-1)计算欧拉函数的公式1.若一个数m可以写成m=(为素数)，则2.对任一正整数m，若其可写成，则欧拉定理对于任何互素的两个整数a和n，有当n为素数时，欧拉定理相当于费马定理求7803的后三位数字求11803的后三位数字思考1、如果今天是星期一，问从今天起再过天是星期几？第七节本原元对于任何互素的两个整数a和n，在方程中，至少有一个正整数m满足这一方程（因为是其中的一个解），那么，最小的正整数解m为模n下a的阶。如果a的阶

15、m=，称a为n的本原元。第八节中国剩余定理《孙子算经》下卷第26题所提出的问题如下:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何？”“答曰：二十三。”相当于求同余方程组n2(mod3)n3(mod5)n2(mod7)23除数余数最小公倍数衍数乘率各总答数最小答数323×5×7＝1055×7235×2×2140＋63＋30＝233233－2×105＝23537×3121×1×2723×5115×1×2例韩信点兵:有兵