密码学中的数论基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数论是密码学特别是公钥密码学的基本工具。,数论概念,:,研究“离散数字集合”,运算是“,+” ,“”,例,:,整数,:,5 + 9 = 14;,5 3 = 5 + 5 + 5 = 15,多项式,:,x,2,+1 + x = x,2,+x+1;,x x,2,+1 = x,3,+x,1.,数论简介,运算概念,运算,:,模数运算,模多项式运算,进一步运算,:,指数运算,逆运算,整除,对整数,b!=0,及,a ,如果存在整数,m,使得,a=,mb,称,b,整除,a,也称,b,是,a,的因子,记作,b|a,例,1,2,3,4,6,8,12,24,整除,24,1.,因子,:,设,a,，,b(b0),是两个整数，如果存在另一整数,m,，,使得,a=,mb,，,则称,b,整除,a,，,记为,b|a,，,且称,b,是,a,的,因子,。,1.1,素数和互素数,整数具有以下性质：,a|1,，,那么,a=1,。,a|b,且,b|a,，则,a=b,。,对任一,b (b0),，,b|0,。,b|g,，,b|h则对任意整数,m,、,n,有,b|(mg+nh,),。,1.1,素数和互素数,这里只给出的证明，其他,3,个性质的证明都很简单。,性质的证明：,由,b|g,，,b|h,知，存在整数,g1,、,h1,，,使得,g=bg1,h=bh1,所以,mg+nh,=mbg1+nbh1 =b(mg1+nh1),因此,b|(mg+nh,),。,1.1,素数和互素数,2.,素数,:,称整数,p(p1),是,素数,，如果,p,的因子只有,1,，,p,。,任一整数,a(a1),都能惟一地分解为以下形式：,其中,p,1,p,2,p,t,是素数，,a,i,0(i=1,t),。,例如,91=711,，,11011=711,2,13,1.1,素数和互素数,这一性质称为整数分解的惟一性，也可如下陈述：设,P,是所有素数集合，则任意整数,a (a1),都能惟一地写成以下形式：,其中,a,p,0,等号右边的乘积项取所有的素数，然而大多指数项,a,p,为,0,。相应地，任一正整数也可由非,0,指数列表表示。例如：,11011,可表示为,a,7,=1,a,11,=2,a,13,=1,。,两数相乘等价于对应的指数相加，即由,k=,mn,可得：对每一素数,p,k,p,=,m,p,+n,p,。,而由,a|b,可得： 对每一素数,p,a,p,b,p,。,这是因为,p,k,只能被,p,j,(jk,),整除。,1.1,素数和互素数,3.,互素数,称,c,是两个整数,a,、,b,的最大公因子，如果,c,是,a,的因子也是,b,的因子，即,c,是,a,、,b,的公因子。,a,和,b,的任一公因子，也是,c,的因子。,表示为,c=,gcd(a, b),。,1.1,素数和互素数,由于要求最大公因子为正，所以,gcd(a,b,)=,gcd(a,-b,)=,gcd(-a,b,)=,gcd(-a,-b,),。,一般,gcd(a,b,)=,gcd(|a|,|b,|),。,由任一非,0,整数能整除,0,，可得,gcd(a,0)=|a|,。,如果将,a,，,b,都表示为素数的乘积，则,gcd(a, b),极易确定。,例如：,300=2,2,3,1,5,2,；,18=2,1,3,2,gcd(18,300)=2,1,3,1,5,0,=6,一般由,c=,gcd(a,b,),可得：,对每一素数,p,，,c,p,=,min(a,p,b,p,),。,1.1,素数和互素数,由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。,如果,gcd(a,b,)=1,，,则称,a,和,b,互素,。,1.1,素数和互素数,整数互素,整数,a, b,互素是指 它们没有除,1,之外的其它因子,8,与,15,互素,8,的因子,1,2,4,8,15,的因子,1,3,5,15,1,是唯一的公因子,素数与不可约多项式,素数,:,只有因子,1,和自身,1,是一个平凡素数,例,2,3,5,7,是素数, 4,6,8,9,10,不是,素多项式或不可约多项式,irreducible,:,不可写成其他因式的乘积,x,2,+x = x x+1,是非不可约多项式,;,x,3,+x+1,是不可约多项式,一些素数,200,以内的素数,:,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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,素数分解,把,整数,n,写成素数的成绩,分解整数要比乘法困难,整数,n,的素数分解是把它写素数的乘积,eg,:,91 = 7 13 ;,3600 = 2,4, 3,2, 5,2,设,n,是一正整数，,a,是整数，如果用,n,除,a,，,得商为,q,，,余数为,r,，,则,a=qn+r,0rn,其中,x,为小于或等于,x,的最大整数。,用,a mod n,表示余数,r,，,则,。,如果,(a mod n)=(b mod n),，,则称两整数,a,和,b,模,n,同余,，记为,ab mod n,。,称与,a,模,n,同余的数的全体为,a,的同余类,，记为,a,，称,a,为这个同余类的,表示元素,。,注意： 如果,a0(mod n),，则,n|a,。,1.2,模运算,同余有以下性质：, 若,n|(a-b),，则,ab mod n,。,(a mod n)(b mod n),，则,ab mod n,。,ab mod n,则,ba mod n,。,ab mod n,bc mod n,则,ac mod n,。,从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。,1.2,模运算,求余数运算（简称求余运算）,a mod n,将整数,a,映射到集合,0,1, ,n-1,，,称,求余运算,在这个集合上的算术运算为,模运算,，模运算有以下性质：,(a mod n)+(b mod n) mod n=(a+b) mod n,。,(a mod n)-(b mod n) mod n=(a-b) mod n,。,(a mod n)(b mod n) mod n=(ab) mod n,。,1.2,模运算,性质的证明：,设（,a mod n,）,=,r,a,，,(b mod n)=,r,b,，,则存在整数,j,、,k,使得,a=,jn+r,a,，,b=,kn+r,b,。,因此,(a+b) mod n=(,j+k)n+r,a,+r,b, mod n=(,r,a,+r,b,) mod n,=,(a mod n)+(b mod n) mod n,（,证毕）,性质、的证明类似。,1.2,模运算,例：,Z,8,=0,1,7,，,考虑,Z,8,上的模加法和模乘法，结果如下表所示。,1.2,模运算,从加法结果可见，对每一,x,，都有一,y,，使得,x+y0 mod 8,。如对,2,，有,6,，使得,2+60 mod 8,，称,y,为,x,的负数，也称为加法逆元。,+,0,1,2,3,4,5,6,7,0,0,1,2,3,4,5,6,7,1,1,2,3,4,5,6,7,0,2,2,3,4,5,6,7,0,1,3,3,4,5,6,7,0,1,2,4,4,5,6,7,0,1,2,3,5,5,6,7,0,1,2,3,4,6,6,7,0,1,2,3,4,5,7,7,0,1,2,3,4,5,6,对,x,，若有,y,，使得,xy1 mod 8,，如,331 mod 8,，则称,y,为,x,的倒数，也称为乘法逆元。本例可见并非每一,x,都有乘法逆元。,X,0,1,2,3,4,5,6,7,0,0,0,0,0,0,0,0,0,1,0,1,2,3,4,5,6,7,2,0,2,4,6,0,2,4,6,3,0,3,6,1,4,7,2,5,4,0,4,0,4,0,4,0,4,5,0,5,2,7,4,1,6,3,6,0,6,4,2,0,6,4,2,7,0,7,6,5,4,3,2,1,一般地，定义,Zn,为小于,n,的所有非负整数集合，即,Zn=0,1, ,n-1,，称,Zn,为模,n,的同余类,集合。其上的模运算有以下性质：, 交换律,(w+x) mod n=(x+w) mod n,(wx) mod n=(xw) mod n,结合律,:,(w+x)+y mod n=w+(x+y) mod n,(wx)y mod n=w(xy) mod n,1.2,模运算,分配律,w(x+y) mod n=wx+wy mod n,单位元,(0+w) mod n=w mod n,(1w) mod n=w mod n,加法逆元 对,wZn,，,存在,zZn,，,使得,w+z0 mod n,，记,z=-w,。,1.2,模运算,此外还有以下性质：,如果,(a+b)(a+c) mod n,，则,bc mod n,，,称为,加法的可约律,。,该性质可由,(a+b)(a+c) mod n,的两边同加上,a,的加法逆元得到。,1.2,模运算,然而类似性质对乘法却不一定成立。例如,63672 mod 8,，,但,37 mod 8,。,原因是,6,乘以,0,到,7,得到的,8,个数仅为,Z8,的一部分，见上例。,即如果将对,Z,8,作,6,的乘法,6Z,8,（,即用,6,乘,Z,8,中每一数）看作,Z,8,到,Z,8,的映射的话，,Z,8,中至少有两个数映射到同一数，因此该映射为多到一的，所以对,6,来说，没有惟一的乘法逆元。但对,5,来说，,551 mod 8,，,因此,5,有乘法逆元,5,。,仔细观察可见，与,8,互素的几个数,1,，,3,，,5,，,7,都有乘法逆元。,这一结论可推广到任一,Zn,。,1.2,模运算,定理,1,设,aZn,，,gcd(a, n)=1,，则,a,在,Zn,中有乘法逆元。,证明： 首先证明,a,与,Zn,中任意两个不相同的数,b,、,c,（,不妨设,cb,）,相乘，其结果必然不同。否则设,abac mod n,，,则存在两个整数,k,1,k,2,，,使得,ab,=k,1,n+r,，,ac=k,2,n+r,，,可得,a(b-c)=(k,1,-k,2,)n,，,所以,a,是,(k,1,-k,2,)n,的一个因子。,1.2,模运算,又由,gcd(a,，,n)=1,，得,a,是,k,1,-k,2,的一个因子，设,k,1,-k,2,=k,3,a,，所以,a(b-c,)=k,3,an,，即,b-c,=k,3,n,，与,0cbn,矛盾。,所以,|,aZn,|=|Zn|,，又知,aZnZn,，所以,aZn,=Zn,。因此对,1Zn,，存在,xZn,，使得,ax1 mod n,，即,x,是,a,的乘法逆元。记为,x=a,-1,。 （证毕）,1.2,模运算,设,p,为一素数，则,Zp,中每一非,0,元素都与,p,互素，因此有乘法逆元。类似于,加法可约律,，可有以下,乘法可约律,：,如果,(ab)(ac) mod n,且,a,有乘法逆元，那么对,(ab)(ac) mod n,两边同乘以,a,-1,，,即得,bc mod n,1.2,模运算,模算式,除法取余运算,同余,(,congruence),for,a = b mod n,如果,a,b,除以,n,余数相同,eg,.,100 = 34 mod 11,b,叫做,a,模,n,的剩余,通常,0=b=n-1,eg,.,-12mod7 = -5mod7 = 2mod7 = 9mod7,可以进行整数运算,模运算举例,-21 -20 -19 -18 -17 -16 15,-14 -13 -12 -11 -10 -9 -8,-7 -6 -5 -4 -3 -2 -1,0 1 2 3 4 5 6,7 8 9 10 11 12 13,14 15 16 17 18 19 20,21 22 23 24 25 26 27,28 29 30 31 32 33 34,模算术运算,加法,a+b,mod n,减法,a-b mod n = a+(-b) mod n,乘法,除法,乘法,a.b mod n,重复加法,除法,a/b mod n,乘以,b,的逆元,:,a/b = a.b,-1,mod n,如果,n,是素数,b,-1,mod n,存在,s.t,b.b,-1,= 1 mod n,例,.,2.3=1 mod 5 hence 4/2=4.3=2 mod 5,模递归运算,模递归运算是“模除求余”,例,.r = a mod n,计算,a = d.n + r,33 mod 7 = 4.7 + 5;,得数是,5,通常,r,取,正数,例,-18 mod 7 = -3.7 + 3;,答案是,3,a+/-b mod n = a mod n +/- b mod n mod n,费尔玛,(Fermat),定理,和,欧拉,(Euler),定理,在公钥密码体制中起着重要作用。,Fermat,定理：若,p,是素数，,a,是正整数且,gcd(a, p)=1,，则,a,p-1,1 mod p,。,Euler,定理：若,a,和,n,互素，则,a,(n),1 mod n,。,1.3,费尔玛定理和欧拉定理,费尔玛定理,证明：,当,gcd(a, p)=1,时,aZp,=,Zp,，,其中,aZp,表示,a,与,Zp,中每一元素做模,p,乘法。又知,a00 mod p,，,所以,aZp-0=Zp-0,，,a(Zp-0)=Zp-0,。即,a mod p,2a mod p,(p-1)a mod p =1,2,p-1,例如,P=7,a=3,3,6,9,12,15,18mod 7=3,6,2,5,1,4,费尔玛定理,所以,a2a(p-1)a(a mod p),(2a mod p)(p-1)a mod p) mod p (p-1)! mod p,另一方面,a2a(p-1)a=(p-1)!a,p-1,因此,(p-1)!a,p-1,(p-1)! mod p,由于,(p-1)!,与,p,互素，因此,(p-1)!,有乘法逆元，由乘法可约律得,a,p-1,1 mod p,。 （,证毕）,费尔玛定理,Fermat,定理也可写成如下形式： 设,p,是素数，,a,是任一正整数，则,a,p,a,mod p,。,费尔玛定理,2.,欧拉函数,设,n,是一正整数，小于,n,且与,n,互素的正整数的个数称为,n,的,欧拉函数,，记为,(n),。,例如：,(6)=2,，,(7)=6,，,(8)=4,。,若,n,是素数，则显然有,(n)=n-1,。,欧拉定理,定理,4.3,若,n,是两个素数,p,和,q,的乘积，则,(n)=(p)(q)=(p-1)(q-1),。,证明：考虑,Zn=0,1,pq-1,，,其中不与,n,互素的数有,3,类，,A=p,2p,(q-1)p,，,B=q,2q,(p-1)q,C=0,，且,AB=,，,否则,ip,=,jq,，,其中,1iq-1,，,1jp-1,则,p,是,jq,的因子，因此是,j,的因子，设,j=kp,，,k1,。则,ip,=,kpq,，,i=,kq,，,与,1iq-1,矛盾。所以,(n)=|Zn|-|A|+|B|+|C|=pq-(q-1)+(p-1)+1,=(p-1)(q-1)=(p)(q),（,证毕）,欧拉定理,例如： 由,21=37,，得,(21)=(3)(7)=26=12,。,欧拉定理,3.,欧拉定理,（,Euler,）,若,a,和,n,互素，则,a,(n),1 mod n,。,证明： 设,R=x1,x2,x,(n),是由小于,n,且与,n,互素的全体数构成的集合，,aR=ax,1,mod n,ax,2,mod n,ax,(n),mod n,，对,aR,中任一元素,ax,i,mod n,，因,a,与,n,互素，,x,1,与,n,互素，所以,ax,i,与,n,互素，且,ax,i,mod nd,。,Euclid,（,f, d,）,1. Xf; Yd,；,2. if Y=0 then return X=,gcd(f,d,),；,3. R=X mod Y,；,4. X=Y,；,5. Y=R,；,6.,goto,2,。,1.5,欧几里得算法,例： 求,gcd(1970, 1066),。,1970=11066+904, gcd(1066, 904),1066=1904+162,gcd(904, 162),904=5162+94,gcd(162, 94),162=194+68,gcd(94, 68),94=168+26,gcd(68, 26),68=226+16,gcd(26, 16),26=116+10,gcd(16, 10),16=110+6, gcd(10, 6),10=16+4,gcd(6, 4),6=14+2,gcd(4, 2),4=22+0,gcd(2, 0),因此,gcd(1970, 1066)=2,。,1.5,欧几里得算法,2.,求乘法逆元,如果,gcd(a, b)=1,，则,b,在,mod a,下有乘法逆元（不妨设,ba,），,即存在一,x (xd,）,1. (X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);,2. if Y3=0 then return X3=,gcd(f, d),；,no inverse;,3. if Y3=1 then return Y3=,gcd(f, d),；,Y2=d-1 mod f;,4. Q=X3Y3,；,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.,goto,2,。,1.5,欧几里得算法,算法中的变量有以下关系：,fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3,在算法,EUCLID (f, d),中，,X,等于前一轮循环中的,Y,，,Y,等于前一轮循环中的,X mod Y,。,而在算法,Extended Euclid(f, d),中，,X3,等于前一轮循环中的,Y3,，,Y3,等于前一轮循环中的,X3-QY3,，,由于,Q,是,Y3,除,X3,的商，因此,Y3,是前一轮循环中的,Y3,除,X3,的余数，即,X3 mod Y3,，,可见,Extended Euclid(f, d),中的,X3,、,Y3,与,Euclid(f, d),中的,X,、,Y,作用相同，因此可正确产生,gcd(f, d),。,1.5,欧几里得算法,如果,gcd(f, d)=1,，,则在最后一轮循环中,Y3=0,，,X3=1,，,因此在前一轮循环中,Y3=1,。由,Y3=1,可得,: fY1+dY2=Y3,，,fY1+dY2=1,，,dY2=1+(-Y1)f,，,dY21 mod f,，,所以,Y2d,-1,mod f,。,1.5,欧几里得算法,例： 求,gcd(1769, 550),。,算法的运行结果及各变量的变化情况如表,42,所示。（见,83,页表,4.2,）,所以,gcd(1769,550)=1,，,550,-1,mod 1769=550,。,1.5,欧几里得算法,中国剩余定理,是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。,例如：,Z,10,中每个数都可从这个数关于,2,和,5,（,10,的两个互素的因子）的同余类重构。比如已知,x,关于,2,和,5,的同余类分别是,0,和,3,，即,x mod 20,，,x mod 53,。,可知是偶数且被,5,除后余数是,3,，所以可得,8,是满足这一关系的惟一的,x,。,1.6,中国剩余定理,定理,4.5,（中国剩余定理） 设,m,1,m,2,m,k,是两两互素的正整数，,，,则一次同余方程组,对模,M,有惟一解,:,其中,ei,满足,1.6,中国剩余定理,证明：设,i=1,2,k,，,由,Mi,的定义得,Mi,与,mi,是互素的，可知,Mi,在模,mi,下有惟一的乘法逆元，即满足,的,ei,是惟一的。,1.6,中国剩余定理,下面证明对,i1,2,k,，,上述,x,满足,a,i,(mod,m,i,)x,。,注意到当,ji,时，,m,i,|M,j,，即,M,j,0(mod m,i,),。,所以,(,M,j,e,j,mod,m,j,) mod m,i,(,M,j,mod,m,i,)(e,j,mod,m,j,) mod m,i,) mod m,i,0,而,(,M,i,(e,i,mod m,i,) mod,m,i,(M,i,e,i,) mod m,i,1,所以,x(mod,m,i,)a,i,，即,a,i,(mod,m,i,)x,1.6,中国剩余定理,下面证明方程组的解是惟一的。设,x,是方程组的另一解，即,xai(mod,m,i,)(i=1,2,k),由,xa,i,(mod,mi),得,x-x0(mod m,i,),，即,m,i,|(x-x),。,再根据,mi,两两互素，有,M|(x-x),，即,x-x0(mod M),，,所以,x(mod M)=,x(mod,M),。,(,证毕,),1.6,中国剩余定理,中国剩余定理提供了一个非常有用的特性，,即在模,M,下可将非常大的数,x,由一组小数,(a,1,a,2,a,k,),表达,。,1.6,中国剩余定理,例： 由以下方程组求,x,。,解：,M=2357=210,，,M,1,=105,，,M,2,=70,，,M,3,=42,，,M,4,=30,易求,e,1,M,-1,1,mod 21,e,2,M,-1,2,mod 31,e,3,M,-1,3,mod 53,e,4,M,-1,4,mod 74,所以,x mod 210(10511+7012+4233+3045) mod 210173,，,或写成,x173 mod 210,。,1.6,中国剩余定理,例： 将,973 mod 1813,由模数分别为,37,和,49,的两个数表示。,解： 取,x=973, M=1813, m1=37,m2=49,。,由,a1973 mod m111,a2973 mod m342,得,x,在模,37,和模,49,下的表达为（,11,42,）。,1.6,中国剩余定理,1.,求模下的整数幂,Euler,定理指出如果,gcd(a, n)=1,，则,a,(n),1 mod n,。,现在考虑如下的一般形式,:,a,m,1 mod n,如果,a,与,n,互素，则至少有一整数,m,（,比如,m=(n),）,满足这一方程。称满足方程的最小正整数,m,为模,n,下,a,的阶。,1.7,离散对数,例如：,a=7,，,n=19,，,则易求出,7,1,7 mod 19,7,2,11 mod 19,7,3,1 mod 19,，,即,7,在模,19,下的阶为,3,。,由于,7,3+j,=7,3,7,j,7,j,mod 19,所以,7,4,7 mod 19,7,5,7,2,mod 19, ,即从,7,4,mod 19,开始所求的幂出现循环，循环周期为,3,，即循环周期等于元素的阶。,模下的整数幂,定理,4.6,设,a,的阶为,m,，则,a,k,1 mod n,的充要条件是,k,为,m,的倍数。,证明：设存在整数,q,，,使得,k=,qm,，则,a,k,(a,m,),q,1 mod n,。,反之，假定,a,k,1 mod n,，令,k=,qm+r,其中,00,a1),的逆函数称为以,a,为底,x,的对数，记为,y=,log,a,x,。,对数函数有以下性质：,log,a,1=0,log,a,a=1,log,a,xy=,log,a,x+log,a,y,log,a,x,y,=,ylog,a,x,在模运算中也有类似的函数。设,p,是一素数，,a,是,p,的本原根，则,a,a,2,a,p-1,产生出,1,到,p-1,之间的所有值，且每一值只出现一次。因此对任意,b1,p-1,，,都存在惟一的,i(1ip-1),，,使得,ba,i,mod p,。称,i,为模,p,下以,a,为底,b,的指标，记为,i=,ind,a,p,(b,),。,指标,指标有以下性质：,ind,a,p,(1)=0,。,ind,a,p,(a,)=1,。,分别由以下关系得出：,a,0,mod p=1 mod p=1,a,1,mod p=a,。,以上假定模数,p,是素数，对于非素数也有类似的结论。,指标,例： 设,p=9,，则,(p)=6,，,a=2,是,p,的一个本原根，,a,的不同的幂为（模,9,下）,2,0,1,2,1,2,2,2,4,2,3,8,2,4,7,2,5,5,2,6,1,由此可得,a,的指数表如下所示。,指标,x,1,2,4,5,7,8,ind,2,9,(x),0,1,2,5,4,3,ind,5,9,(x),0,5,4,1,2,3,在讨论指标的另两个性质时，需要利用如下结论： 若,a,z,a,q,mod p,，,其中,a,和,p,互素，则有,zq mod (p),。,证明：因,a,和,p,互素，所以,a,在模,p,下存在逆元,a,-1,，在,a,z,a,q,mod p,两边同乘以,(a,-1,),q,，得,a,z-q,1 mod p,。由,Euler,定理,a,(p),1 mod p,知存在一整数,k,，使得,z-qk(p,),，所以,zq,mod,(p,),。,指标,由上述结论可得指标的以下两个性质：,ind,a,p,(xy,)=,ind,a,p,(x)+ind,a,p,(y,) mod (p),。,ind,a,p,(y,r,)=,rind,a,p,(y,) mod (p),。,性质是性质的推广。,从指标的以上性质可见，指标与对数的概念极为相似。,指标,性质的证明：设,由模运算的性质得：,所以,ind,a,p,(xy,)=,ind,a,p,(x)+ind,a,p,(y,) mod (p),（,证毕）,指标,3.,离散对数,设,p,是素数，,a,是,p,的本原根，即,a,1,a,2,a,p-1,在,mod p,下产生,1,到,p-1,的所有值，所以对,b1,p-1,，,有惟一的,i1,p-1,使得,ba,i,mod p,。称,i,为模,p,下以,a,为底,b,的离散对数，,记为,ilog,a,b(mod,p),。,离散对数,当,a,、,p,、,i,已知时，用快速指数算法可比较容易地求出,b,，但如果已知,a,、,b,和,p,，求,i,则非常困难。目前已知的最快的求离散对数算法其时间复杂度为：,所以当,p,很大时，该算法也是不可行的。,离散对数,设,p,是一素数，,a,小于,p,，称,a,是,p,的平方剩余,，如果方程,x,2,a (mod p),有解。否则称为非平方剩余。,1.8,平方剩余,求离散对数的,shank,算法,求,5x mod 23=3,m=4;,L:=array(1.4,50 mod 23,51 mod 23,52 mod 23,53 mod 23)=,1,5,2,10,;,A:=5(22-4) mod 23=,6,;,3*6 mod 23=18;18*6 mod 23=16;,16*6 mod 23=4;4*6 mod 23=1;,q:=4;x:=q*d+0;,516 mod 23 =3;,1.8,平方剩余,定义：设,n2,若,x,2,a(mod n),有解,则称,a,是模,p,的二次剩余,;,若无解,则称,a,是模,p,的二次非剩余,.,二次剩余集合,QR,n,二次非剩余集合,QNR,n,.,容易证明，模,p,的平方剩余的个数为,(p-1)/2,，,且与模,p,的非平方剩余的个数相等。如果,a,是模,p,的一个平方剩余，那么,a,恰有两个平方根，一个在,0,到,(p-1)/2,之间，另一个在,(p-1)/2,到,(p-1),之间，且这两个平方根中的一个也是模,p,的平方剩余。,1.8,平方剩余,欧拉准则,定理,(,欧拉准则,),设,p,为一奇素数, p,不能整除,x,则有,: x,属于,QR,p,证明,:,（,1,）,若存在,y,2,x(mod p),（,2,）若 ，但,y,2,x(mod p),无解,对任意,1 i p-1,总有一整数,j,使得,:,ij,x(mod,p).,由于,y,2,x(mod p),无解,.,故,ij.,因此, 1,2,p-1,可分成,(p-1)/2,对,每对之积,(mod p).,因此, (p-1)! a,(p-1)/2,1(mod p).,根据威尔逊定理知, (p-1)! -1(mod p),所以命题得证,.,定义,1,设,p,是素数，,a,是一整数，符号 的定义如下：,称符号 为,Legendre,符号。,1.8,平方剩余,例如：,计算 有一个简单公式：,例如：,p=23,，,a=5,，,a,(p-1)/2,mod p,5,11,mod p=-1,，,所以,5,不是模,23,的平方剩余。,1.8,平方剩余,为了简化“,x,2,a,(mod p),有解”这一较长的说法,今引人勒让德,(Legendre),符号,其定义如下,:,设,p,为奇素数,且,p,不能整除,a,则,:,当,a,是模户二次剩余,;,当,a,是模,p,二次非剩余,.,例如, ,因为,x,2,3(mod 5),无解,;,因为,1,是模,5,的二次剩余,.,勒让德符号,下面给出,Legendre,符号的三条简单而又重要的性质,定理,6.16,若,a,b(mod p),则,若,p,不能整除,a,则,若,p,不能整除,a,与,b,则,:,类似可证,若, a,b(mod p),则,.,显然,若, a,b(mod p),则,由欧拉准则知,:,故,:,由于同余式两端只能是,1,或,-1,这两数对模,p,要同余,只有相等就行,故有,:,表明了,两个剩余的乘积是剩余,;,两个非剩余的乘积也是一剩余,;,一个剩余和一个非剩余的乘积是一非剩余,.,若 其中,是素数, 1in,则有,:,因为 所以任给一整数,a,计算,只需要计算出三种值,:,其中,q,为奇素数,.,对于每一奇素数,p,则有,:,若,p,1(mod 4),若,p,3(mod 4),证明,由欧拉准则知,由于, (p-1)/2,是偶数还是奇数取决于,p,与,1,是模,4,同余还是,p,与,3,模,4,同余,.,(,高斯引理,),设,p,为奇素数, p,不能整除,a,若,a,2a,(p-1)/2*a,的模,p,非负最小剩余有,m,个大于,(p-1)/2,则,:,若,p,是奇素数,则,(,高斯二次互反定理,),若,p,和,q,是二奇素数,且,pq,则有,:,该定理是说, p,q3(mod 4),则二同余式,:,x2p(mod p), x2q(mod p),中一有解,一无解,.,不然,则皆有解,或皆无解,.,例,.,验证,x,2,85(mod 97),有解,.,证明,:,若 则证明即完成,.,因为 而,97 1(mod 4),故有二次互,反,定理知,又由,而,当,p,5(mod 8),时, a,(p-1)/4,-1(mod p),时, a,(p+3)/8,为,x,2,a(mod p),的解,;,设,则有,:,当,p,3(mod 4),时, a,(p-1)/4,为,x,2,a(mod p),的解,.,当,p,5(mod 8),时, a,(p-1)/4,1(mod p),时, a,(p+3)/8,为,x,2,a(mod p),的解,;,设,p,1(mod 8),则同余式有,x,2,a(mod p),解,a,(q+1)/2,b,t,e,其中,q,满足,: p=2,k,q+1, q,是奇数, t,e,0,是某个整数,.,证明,:,由,p1(mod 8),可设,p=2,e,q+1, e,3,2,不能整除,q,由 得出,:,于是,若,则,所以存在非负整数,使得,于是,故有非负整数,使下式成立,:,因为,e,是有限整数,故必有一非负整数,t,e,使得,:,a,q,b,2t,e,1(mod p),于是得,:,a,q+1,b,2t,e,a(mod p),即,:,(a,(q+1)/2,b,t,e,),2,a(mod p),例,.,解,x,2,85(mod 97),97,96,1,2,5,3,1,Shank,算法,设,p=2,e,q+1,，,设,g,是,G,的生成元,有唯一的阶为,2,e,的循环子群,G,，,存在整数,r,g,如何确定？,若,取,即可,k,如何确定？,取,找最小的,m,设,找最小的,m,1,取,重复过程，知道找到,例,.,解,x,2,85(mod 97),97,96,1,2,5,3,1,