密码学数学基础.ppt

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

2、i，i = 1, 2, , n ma1q1 a2q2 anqn， 此处qiZ（i = 1, 2, , n）。,5,第一节 整除与带余数除法,注： ab ab； ba bcac，此处c是任意的非零整数； ba，a 0 |b| |a|； ba且|a| |b| a = 0。,6,第一节 整除与带余数除法,定理2(带余数除法) 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 a = bq r，0 r b。 (1) 此外，ba的充要条件是r=0,7,第二节 素数,如果正整数P 1只能被1和它本身整除，则该数为素数（也叫质数） 100以内的素数有25个，分别是2、3、5、7、11、13、17

3、、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89和97。,8,任何大于1的整数a都可以分解成素数幂之积，且唯一。 其中，pi为素数，ai为正整数。,9,第三节 最大公因数,定义1 设a1, a2, , an是n（n2）个整数，若整数d是它们之中每一个的因数，则d就叫做a1, a2, , an的一个公因数；其中最大的一个公因数叫做a1, a2, , an的最大公因数。记为(a1, a2, , an)。 由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，且是正整数。,10,最大公因数,若(a1, a2, , an) = 1， 则称a

4、1, a2, , an是互质的； 若(ai, a j) = 1，1 i, j n，i j， 则称a1, a2, , an是两两互质的。 显然，a1, a2, , an两两互质可以推出(a1, a2, , an) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2。,11,最大公因数,由上我们容易得到： 定理 （裴蜀（Bzout,1730-1783）恒等式）设a，b是任意两个不全为零的整数，则存在s，tZ，使得 as bt = (a, b),12,最大公因数,推论 (a, b)1的充要条件是：存在s，tZ，使得 as bt = 1。 此题可以推广为： 推论 (a1, a

5、2, , an) = 1的充要条件是：存在整数x1, x2, , xn，使得 a1x1 a2x2 anxn = 1。,13,欧几里德公式,14,第四节 模运算,令整数 及 ，若 (k为任一整数)，则称 在mod n下与b同余，记为 性质：,，,。,15,例（7+9）mod11 （79）mod11 计算 97 mod 13 证明 13200-1 是51的倍数,16,例 说明 是否被641整除。 解 ： 22 4，24 16，28 256，216 154，232 1 (mod 641)。 因此 0 (mod 641)， 即641,17,例 求(25733 46)26 mod 50 解： (2573

6、3 46)26 (733 4)26 = 7(72)16 426 7( 1)16 426 = (7 4)26 326 = 3(35)5 3(7)5 = 37(72)2 21 29 (mod 50)， 即所求的余数是29。,18,第五节 模逆元,模逆元的计算可以通过扩展欧几里德算法实现。,19,第六节 费马欧拉定理,费马定理 如果p是素数，且p不能被a整除，那么,20,欧拉函数 表示比m小，且与m互素的正整数的个数 欧拉函数性质： 当m是素数时， =m-1 当m=pq，且p、q（pq）均为素数时， = =(p-1)(q-1),21,计算欧拉函数的公式 1. 若一个数m可以写成m= ( 为素数)，则

7、 2.对任一正整数m，若其可写成， 则,22,欧拉定理 对于任何互素的两个整数a和n，有 当n为素数时，欧拉定理相当于费马定理,23,求7803的后三位数字 求11803的后三位数字,24,思考 1、如果今天是星期一，问从今天起再过 天是星期几？,25,第七节 本原元,对于任何互素的两个整数a和n，在方程 中，至少有一个正整数m满足这一方程（因为 是其中的一个解），那么，最小的正整数解m为模n下a的阶。如果a的阶m= ，称a为n的本原元。,26,第八节 中国剩余定理,孙子算经下卷第26题所提出的问题如下: “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二。问物几何？” “答曰：

8、二十三。”,27,相当于求同余方程组 n 2 (mod 3) n 3(mod 5) n 2 (mod 7) 23,28,29,例 韩信点兵:有兵一队, 若列成五行纵队, 则末行一人; 成六行纵队, 则末行五人; 成 七行纵队,则末行四人; 成十一行纵队,则末 行十人, 求兵数.,30,x=2100+2310k, k=0,1,2,.,31,解 设x是所求兵数, 则依题意: x1(mod 5), x 5(mod 6)，x4(mod 7), x 10(mod 11) 令m1=5, m2=6, m3=7, m4=11, b1=l, b2=5, b3=4, b4=10.,32,于是m=m1m2m3m4=56711=2310, M1=2310/5=462, M2=385, M3=330, M4=210. 有M1 M11(mod 5), 即14