应用密码学第7讲

12010-2011年度济南大学网络工程专业本科班课程应用密码学第七讲数论简介贾忠田济南大学信息科学与工程学院电子信箱：[e-mail]2本讲主要内容：素数和互素模运算费尔马定理和欧拉定理素性检验欧几里得算法中国剩余定理离散对数平方剩余3一、素数和互素数1.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。整数具有以下性质：①a|1，那么a=±1。②a|b且b|a，则a=±b。③对任一b(b≠0)，b|0。④b|g，b|h，则对任意整数m、n有b|(mg+nh)。42.素数称整数p(p1)是素数，如果p的因子只有±1，±p。1212ttappp任一整数a(a1)都能惟一地分解为以下形式：其中p1p2…pt是素数，ai0(i=1,…,t)。例如91=13×7，11011=13×112×7这一性质称为整数分解的惟一性。这一性质也可表示为：papPap5两数相乘等价于这两个数的分解式中相同因子的指数相加，即由k=mn可得，对每一素因子p,kp=mp+np。例如：2435m23532n235)235)(35(563224mnk2,435mm3,235nn5,635kk(1)(2)由（1）和（2）式得：555nmk333nmk6若a|b，且a和b的分解式中，都有素p的幂，则对每一素数p的幂指数ap和bp,有ap≤bp。例如：15|45，15=5X345=5X3^23.互素数称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。规定c07如果gcd(a,b)=1，则称a和b互素。二、模运算设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤rn,用amodn表示余数r如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。8同余有以下性质：①若n|(a-b)，则a≡bmodn。②(amodn)≡(bmodn)，则a≡bmodn。③a≡bmodn,则b≡amodn。④a≡bmodn,b≡cmodn,则a≡cmodn。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。9求余数运算（简称求余运算）amodn将整数a映射到集合{0,1,…,n-1}，称求余运算在这个集合上的算术运算为模运算。例如：a模8的运算将整数a映射到{0,1,2,3,4,5,6,7}上。{…-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9…}{0,1,2,3,4,5,6,7}…-9=q*8+r0=r8=q=-2,r=7-8=q*8+r0=r8=q=-1,r=010模运算有以下性质：①[(amodn)+(bmodn)]modn=(a+b)modn。②[(amodn)-(bmodn)]modn=(a-b)modn。③[(amodn)×(bmodn)]modn=(a×b)modn。例4.1设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法.一般地，定义Zn为小于n的所有非负整数集合，即Zn={0,1,…,n-1}，称Zn为模n的同余类集合。其上的模运算有以下性质：11①交换律(w+x)modn=(x+w)modn(w×x)modn=(x×w)modn②结合律[(w+x)+y]modn=[w+(x+y)]modn[(w×x)×y]modn=[w×(x×y)]modn③分配律[w×(x+y)]modn=[w×x+w×y]modn④单位元(0+w)modn=wmodn(1×w)modn=wmodn⑤加法逆元对w∈Zn，存在z∈Zn，使得w+z≡0modn，记z=-w。12定理4-1设a∈Zn，gcd(a,n)=1，则a在Zn中有乘法逆元。例如：模8的乘法运算，1，3，5，7有逆元。X0123456700000000010123456720246024630361472540404040450527416360642064270765432113三、费尔玛定理和欧拉定理定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。例如：7是个素数，在Z7中，3是正整数且gcd(3,7)=1173=3X3X3X3X3X3=27X27=729729=104X7+1729≡1mod7与p互素的正整数a的p-1次幂在模p的乘法运算下等于单位元1。1.费尔玛定理142.欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。定理4.3若n是两个素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)例如：φ(21)=φ(3)×φ(7)小于21且与21互素的正整数：1，2，4，5，8，10，11，13，16，17，19，20若n是素数，则显然有φ(n)=n-1。153.欧拉定理定理4.4（Euler）若a和n互素，则aφ(n)≡1modn。φ(n)=441Mod8=143Mod8=145Mod8=147Mod8=49X49mod8=1例如：Z8={0,1,2,3,4,5,6,7},n=8,16四、素性检验素性检验是指对给定的数检验其是否为素数。对于大数的素性检验来说没有简单直接的方法，本节介绍一个概率检验法引理如果p为大于2的素数，则方程x2≡1(modp)的解只有x≡1和x≡-1。注意：x≡1与x=1不同。-2≡1mod3因为：-2=-13+1同理：2≡-1mod3逆否命题：如果方程x2≡1modp有一解x0{-1,1}，那么p不为素数。17Witness素性检测算法：Booleanwitness(inta,intn){//a为小于n的整数，n为待检验的数bkbk-1…b0=DectoBi(n-1)；//把n-1转换成2进制d=1;for(i=k;i0;i--){intx=d;d=(dd)modn;ifd==1andx1andxn-1thenreturnFalse;ifbi=1thend=(da)modn;}ifd1thenreturnFalse;returnTrue;}//若返回True，则肯定不是素数。18五、欧几里得算法1.求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。例如：gcd(18,12)=gcd(12,18mod12)=gcd(12,6)=gcd(6,12mod6)=gcd(6,0)=6Euclid算法就是用这种方法，因gcd(a,b)=gcd(|a|,|b|)，因此可假定算法的输入是两个正整数，设为d，f，并设fd。19IntEuclid（f,d）{IntX=f;intY=d；ifY=0thenreturnX；R=XmodY；X=Y；Y=R；goto2;}202.求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元(不妨设ba），即存在一x(xa)，使得bx≡1moda。Euclid推广算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。21Extended_Euclid(f,d){（设fd）1.(X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);2.ifY3=0thenreturnX3=gcd(f,d),noinverse;3.ifY3=1thenreturnY3=gcd(f,d),Y2=dmodf;4.Q=；5.(T1,T2,T3)←(X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3)←(Y1,Y2,Y3);7.(Y1,Y2,Y3)←(T1,T2,T3);8.goto2;}133YX22例如：f=7,d=21.(X1,X2,X3)=(1,0,7);(Y1,Y2,Y3)=(0,1,2);2.ifY3=0thenreturnX3=gcd(f,d),noinverse;X3.ifY3=1thenreturnY3=gcd(f,d),Y2=dmodf;X4.Q==3；33YX5.(T1,T2,T3)=(X1-QY1,X2-QY2,X3-QY3)=(1,-3,1);6.(X1,X2,X3)=(Y1,Y2,Y3)=(0,1,2);7.(Y1,Y2,Y3)=(T1,T2,T3)=(1,4,1);8.goto2符合3，返回Y2（2的逆），Y3（7和2的最大公约数）=(1,4,1)23六、中国剩余定理定理4.5设m1,m2,…,mk是两两互素的正整数，1kiiMm则一次同余方程组1122modmodmodkkamxamxamx对模M有惟一解:112212modkkkMMMxeaeaeaMmmm其中ei满足1mod1,2,,iiiMemikm24中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,…,ak)表达。例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如：已知x关于2和5的同余类分别是[0]和[3]，即xmod2≡0，xmod5≡3。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。25例4.4由以下方程组求x。1mod22mod33mod55mod7xxxx解：M=2·3·5·7=210M1=210/2=105同理：M2=70，M3=42，M4=30求出e1≡M-11mod2≡1,e2≡M-12mod3≡1,e3≡M-13mod5≡3,e4≡M-14mod7≡4,所以x≡(105×1×1+70×1×2+42×3×3+30×4×5)mod210即：x≡173mod21026七、离散对数1.求模下的整数幂Euler定理指出如果gcd(a,n)=1，则aφ(n)≡1modn。现在考虑如下的一般形式:am≡1modn如果a与n互素，则至少有一整数m（比如m=φ(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。例如：a=7，n=19，则易求出71≡7mod19,72≡11mod1973≡1mod19，即7在模19下的阶为3。27由于73+j=73·7j≡7jmod19,所以74≡7mod19,75≡72mod19,…,即从74mod19开始所求的幂出现循环，循环周期为3，即循环周期等于元素的阶。定理4.6设a的阶为m，则ak≡1modn的充要条件是k为m的倍数。推论：a的阶m整除φ(n)。这是因为aφ(n)=1modn如果a的阶m等于φ(n)，则称a为n的本原根。如果a是n的本原根，则a,a2,…,aφ(n)在modn下互不相同且都与n互素。28特别地，如果a是素数p的本原根，则a,a2,…,ap-1在modp下都不相同。例如：n=19,a=3在mod19下的幂为：3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,1即3的阶为18=φ(19)，可验证19的本原根还有：2，10，13，14，15注意：并非所有的整数都有本原根，只有以下形式的整数才有本原根：2,4,pα,2pα其中p为奇素数。292.指标首先回忆一下一般对数的概念，指数函数y=ax(a0,a≠1)的逆函数称为以a为底x的对数，记为y=logax在模运算中也有类似的函数。设p是一素数，a是p的本原根，则a,a2,…,ap-1产生出1到p-1之间的所有值，且每一值只出现一次。因此对任意b∈{1,…,p-1}，都存在惟一的i(1≤i≤p-1)，使得b≡aimodp。称i为模p下以a为底b的指标，记为i=inda，p