2010-第2周 密码学中的数学基础知识

1密码学中的数学知识2因子若b|a,则称b为a的因数若a=kb,而b既非a又非1,则称b是a的真因数.例如12的因子：1，2，3，4，6，1212的真因子：2，3，4，63整除实例Q:下面哪个是对的?77|77|7724|240|2424|04实例Q:1.找出60的所有因子2.列出80的所有真因子5模运算设n是正整数，a是整数，如果用n去除a，得商为q，余数为r，则可以表示为：a=qn+r,0≤rn,用amodn表示余数r，则r≡amodn.例如：令a=17,n=5,则17=3×5+2,r=2≡17mod56模运算典型实例时钟模12的运算7同余设n是正整数，a,b是整数，如果amodn≡bmodn，则称整数a和b模n同余，记为a≡bmodn。显然，a≡bmodn，则n|(a-b).例如：a=17,b=-8,n=5,因为17=3×5+2,-8=-2×5+2,则17mod5≡-8mod5，通常记为：17≡-8mod5.8同余式实例Q:下面哪个是真的?33(mod17)3-3(mod17)172177(mod5)-1313(mod26)9同余式实例A:33(mod17)True.(3-3=0,divisiblebyall)3-3(mod17)False.(3-(-3))=6不能整除17.172177(mod5)True.172-177=-5能整除5-1313(mod26)True:-13-13=-26能整除by26.10同余的基本性质①[(amodn)+(bmodn)]modn=(a+b)modn②[(amodn)-(bmodn)]modn=(a-b)modn③[(amodn)×(bmodn)]modn=(a×b)modn11同余的基本性质例11mod8=3;15mod8=7①[(11mod8)+(15mod8)]mod8=(3+7)mod8=2=(11+15)mod8=26mod8=2②[(11mod8)×(15mod8)]mod8=(3×7)mod8=21mod8=5(11×15）mod8＝165mod8＝512同余性质1.若ab(modm),cd(modm),则:①ax+cybx+dy(modm),其中x和y为任给整数.②acbd(modm).③anbn(modm),其中n＞0.上面的性质容易证明，以②为例：设a=b+q1m,c=d+q2mac=(b+q1m)(d+q2m)=bd+(bq2+dq1+q1q2)m,等式两边同时模m可证。13同余性质2.设m是一个正整数，①ad≡bd(modm),如果(d,m)=1,则a≡b(modm)②a≡b(modm),k0,则ak≡bk(modmk)③a≡b(modm),如果d是m的因子，则a≡b(modd)下面对①③进行证明。14同余性质①证明：若ad≡bd(modm),则m|(ad-bd),即m|d(a-b).因(d,m)=1，故m|(a-b),即a=b(modm)③证明：d是m的因子，故存在m’,使得m=dm’.因为a≡b(modm),存在k,使得a=b+mk=b+dm’k.等式两边模d,可得a≡b(modd).15最大公因数设a,b是整数，则a,b的所有公因数中最大的一个公因数叫做最大公因数，通常记为gcd(a,b)。例如12和-18的最大公因数为6，记为gcd(12,-18)=6gcd(513,614)=？gcd(1024,888)=？如果两个整数的绝对值都比较小，求它们的最大公因数是比较容易的。如果两个数都比较大，可以用广义欧几里德除法，也称辗转相除法。16一个关于同余的性质对任何非负整数a和非负整数b，设a≥b,a=bq+r,0≤r|b|,则gcd（a,b）=gcd(b,r).证明：设gcd（a,b）=d,则d|a,d|b,则d|a-bq即d|r.同理，设gcd(b,r)=k,则k|b,k|r,则k|bq+r,即k|a.所以，结论成立。例如，96=28×3+12，故gcd(96,28)=gcd(28,12)=4.又如，88=11×8+0，故gcd(88,11)=gcd(11,0)=11.17辗转相除法设a,b＞0,且都为整数，进行下列计算:a=bq1+r1,0＜rl＜bb=r1q2+r2,0＜r2＜r1r1=r2q3+r3,0＜r3＜r2…….rn-2=rn-1qn+rn,0＜rn＜rn-1rn-1=rnqn+1+0–则a,b的最大公因数为rn.–因为gcd(a,b)=gcd(b,r1)=gcd(r1,r2)=…=gcd(rn-1,rn)=gcd(rn,0)=rn.18辗转相除法举例例求gcd(184,136)。184=1×136+48,gcd(184,136)=gcd(136,48)136=2×48+40,gcd(136,48)=gcd(48,40)48=1×40+8,gcd(48,40)=gcd(40,8)40=5×8+0,gcd(40,8)=8因此gcd(184,136)=gcd(136,40)=gcd(48,8)=8。19思考：如何用程序实现辗转相除法？20逆元设m是正整数，a是整数，如果存在a’,使得a×a’≡1(modm)成立，则a叫模m的可逆元，a’叫a模m的逆元，a’通常记为a-1。例如，设m为11，则8模11的逆元为7，因为8×7≡1(mod11)，即8-1(mod11)=7例如：2-1mod5＝32-1mod26=？a模m，在什么情况下一定存在乘法逆元呢？21乘法逆实例当a和m互素的情况下，即（a,m）=1,则a的模m的逆元总是存在的。60-1mod89=？用何种算法求乘法逆元？用欧几里德扩展算法求逆22求逆元举例例如，我们知道89是素数，求60模89的逆元，可以用下面方法。89=1×60+2960=2×29+229=14×2+1则1=29-14×2=29-14×(60-2×29)=29×29-14×60=(89-60)×29-14×60=89×29-60×4323求逆元举例等式两端同时mod89得：60×(-43)≡1mod89故60模89的逆元为-43，为方便记为最小非负数，因为-43≡46mod89，故一般说60模89的逆元为46.如何用程序实现求逆元？实际上，这里的逆元通常称为乘法逆元。从后面的学习可以看到，定义不同的运算和单位元，就可能有不同情况下的逆元。24求逆元举例gcd(89,60)Stepx=qy+rxygcd=ax+by0-896025求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+29602926求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+296029260=2·29+229227求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+296029260=2·29+2292329=14·2+12128求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+296029260=2·29+2292329=14·2+12132=2·1+010终止29求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+296029260=2·29+2292329=14·2+1211=29-14·232=2·1+010终止30求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+296029260=2·29+22921=29-14*(60-2*29)=-14*60+29*29329=14·2+1211=29-14·232=2·1+010终止31求逆元举例gcd(89,60)Stepa=qb+rabgcd=xa+yb0-8960189=1·60+2960291=-14*60+29*(89-1*60)=29*89-43*60260=2·29+22921=29-14*(60-2*29)=-14*60+29*29329=14·2+1211=29-14·232=2·1+010终止60mod89的逆32求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-24411733求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+101171034求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+710735求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+7107310=7+37336求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+7107310=7+37347=2·3+13137求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+7107310=7+37347=2·3+13153=3·1+01038求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+7107310=7+37347=2·3+1311=7-2·353=3·1+010终止39求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+7107310=7+3731=7-2·(10-7)=-2·10+3·747=2·3+1311=7-2·353=3·1+010终止40求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117102117=11·10+71071=-2·10+3·(117-11·10)=3·117-35·10310=7+3731=7-2·(10-7)=-2·10+3·747=2·3+1311=7-2·353=3·1+010终止41求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117101=3·117-35·(244-2·117)=-35·244+73·1172117=11·10+71071=-2·10+3·(117-11·10)=3·117-35·10310=7+3731=7-2·(10-7)=-2·10+3·747=2·3+1311=7-2·353=3·1+010终止42求逆元举例gcd(244,117):Stepx=qy+rxygcd=ax+by0-2441171244=2·117+10117101=3·117-35·(244-2·117)=-35·244+73·1172117=11·10+71071=-2·10+3·(117-11·10)=3·117-35·10310=7+3731=7-2·(10-7)=-2·10+3·747=2·3+1311=7-2·353=3·1+010终止inverseof244modulo11743ax=bmodm类方程当（a,m）=1时，ax=1modm类方程的求解就是求逆元。当（a,m）1时，ax=1modm类方程的无解。进而，ax=bmodm类方程有解的条件是：（a,m）|b求解时，如果（a,m）=1，先求ax=bmodm的解，如果（a,m）1且（a,m）|b，暂时不讲44仿射变换求解思考y=kp+bmod26时为什么要求(k,26)=1?45大整数运算实现思考大整数加、减、乘法、除法、模运算，求逆程序