密码学数学基础

密码学数学整数性质•教学目的和要求•（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a2q2anqn，•此处qi∈Z（i=1,2,,n）。第一节整除与带余数除法•注：①abab；②babcac，此处c是任意的非零整数；③ba，a0|b||a|；•ba且|a||b|a=0。第一节整除与带余数除法•定理2(带余数除法)•设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得•a=bqr，0rb。(1)•此外，ba的充要条件是r=0第二节素数•如果正整数P1只能被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。•任何大于1的整数a都可以分解成素数幂之积，且唯一。•其中，pi为素数，ai为正整数。tataapppa2121第三节最大公因数•定义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,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。•欧几里德公式)mod,gcd(),gcd(babba第四节模运算•令整数及，若(k为任一整数)，则称在modn下与b同余，记为•性质：nbamodnnbnanbamod))mod()mod((mod)(nnbnanbamod))mod()mod((mod)(nnbnanbamod))mod()mod((mod)(，。ba,0nknbaa•例（7+9）mod11•（7×9）mod11•计算97mod13•证明13200-1是51的倍数•例说明是否被641整除。•解：•224，2416，28256，216154，2321(mod641)。•因此0(mod641)，•即641125212521252•例求(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是素数，且p不能被a整除，那么papmod11•欧拉函数•表示比m小，且与m互素的正整数的个数•欧拉函数性质：•当m是素数时，=m-1•当m=pq，且p、q（p≠q）均为素数时，•==(p-1)(q-1))(m)(m)(m)(p)(q•计算欧拉函数的公式•1.若一个数m可以写成m=•(为素数)，则•2.对任一正整数m，若其可写成，•则teteeppp2121iptiieippmi11)1()(teteeppp2121iPipmm)11()(•欧拉定理•对于任何互素的两个整数a和n，有•当n为素数时，欧拉定理相当于费马定理nanmod1)(•求7803的后三位数字•求11803的后三位数字•思考•1、如果今天是星期一，问从今天起再过•天是星期几？101010第七节本原元•对于任何互素的两个整数a和n，在方程•中，至少有一个正整数m满足这一方程（因为是其中的一个解），那么，最小的正整数解m为模n下a的阶。如果a的阶m=，称a为n的本原元。nammod1)(n)(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•例韩信点兵:有兵一队,若列成五行纵队,则末行一人;成六行纵队,则末行五人;成七行纵队,则末行四人;成十一行纵队,则末行十人,求兵数.•x=2100+2310k,k=0,1,2,….•解设x是所求兵数,则依题意:•x1(mod5),x5(mod6)，x4(mod7),•x10(mod11)•令m1=5,m2=6,m3=7,m4=11,•b1=l,b2=5,b3=4,b4=10.•于是m=m1m2m3m4=5×6×7×11=2310,•M1=2310/5=462,M2=385,M3=330,M4=210.•有M1’M11(mod5),即1462M1’2M1’(mod5),因此M1’=3.•同理可求M2’=1,M3’=1,M4’=1.故解为:•x1×3×462+1×5×385+1×4×330+1×10×21067312100(mod2310).•即x=2100+2310k,k=0,1,2,….