密码学中的数论基础ppt课件.ppt

《密码学中的数论基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《密码学中的数论基础ppt课件.ppt（111页珍藏版）》请在三一办公上搜索。

1、-,数论是密码学特别是公钥密码学的基本工具。数论概念: 研究“离散数字集合”运算是“+” ,“”例:整数: 5 + 9 = 14; 5 3 = 5 + 5 + 5 = 15 多项式: x2+1 + x = x2+x+1; x x2+1 = x3+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整除

2、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)都能惟一地分解为以下形式：其中p1p2

3、pt是素数，ai0(i=1,t)。例如91=711，11011=711213,1.1 素数和互素数,-,这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a (a1)都能惟一地写成以下形式： 其中ap0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如： 11011可表示为a7=1,a11=2,a13=1。 两数相乘等价于对应的指数相加，即由k=mn 可得：对每一素数p,kp=mp+np。而由a|b可得： 对每一素数p,apbp。这是因为pk只能被pj(jk)整除。,1.1 素数和互素数,-,3. 互素数 称c是两个整

4、数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=223152； 18=2132gcd(18,300)=213150=6一般由c=gcd(a,b)可得： 对每一素数p，cp=min(ap,bp

5、)。,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: 不可写成其他因式的乘积 x2+x = x x+1 是非不

6、可约多项式; x3+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 = 24 32 52,-,-,设n是一正整数，a是整数，如果用n除a，得商为

7、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。 从以上性质易知，同余类中的每一元素都可作为这

8、个同余类的表示元素。,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）=ra，(b mod n)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。因此(a+b) mod n=(j+k)n+ra+

9、rb mod n=(ra+rb) mod n= (a mod n)+(b mod n) mod n （证毕）性质、的证明类似。,1.2 模运算,-,例：Z8=0,1,7，考虑Z8上的模加法和模乘法，结果如下表所示。,1.2 模运算,从加法结果可见，对每一x，都有一y，使得x+y0 mod 8。如对2，有6，使得2+60 mod 8，称y为x的负数，也称为加法逆元。,对x，若有y，使得xy1 mod 8，如331 mod 8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。,-,-,一般地，定义Zn为小于n的所有非负整数集合，即Zn=0,1, ,n-1，称Zn为模n的同余类集合

10、。其上的模运算有以下性质： 交换律 (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，称为加法的可约律。 该

11、性质可由(a+b)(a+c) mod n的两边同加上a的加法逆元得到。,1.2 模运算,-,然而类似性质对乘法却不一定成立。例如63672 mod 8，但37 mod 8。原因是6乘以0到7得到的8个数仅为Z8的一部分，见上例。 即如果将对Z8作6的乘法6Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，551 mod 8，因此5有乘法逆元5。 仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。这一结论可推广到任一Zn。,1.2 模运算,-,定理1 设aZn，gcd(a, n)=1，

12、则a在Zn中有乘法逆元。 证明： 首先证明a与Zn中任意两个不相同的数b、c（不妨设cb）相乘，其结果必然不同。否则设abac mod n，则存在两个整数k1,k2，使得ab=k1n+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。,1.2 模运算,又由gcd(a，n)=1，得a是k1-k2的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0cbn矛盾。 所以|aZn|=|Zn|，又知aZnZn，所以aZn=Zn。因此对1Zn，存在xZn，使得ax1 mod n，即x是a的乘法逆元。记为x=a-1。 （证毕）,1.2

13、 模运算,-,-,设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 -1

14、7 -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

15、 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，则ap-11 mod p。Euler 定理：若a和n

16、互素，则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=33,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)!ap-1

17、 因此 (p-1)!ap-1(p-1)! mod p 由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-11 mod p。 （证毕）,费尔玛定理,-,Fermat定理也可写成如下形式： 设p是素数，a是任一正整数，则apa 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，其中不与

18、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

19、=ax1 mod n,ax2 mod n,ax(n) mod n，对aR中任一元素axi mod n，因a与n互素，x1与n互素，所以axi与n互素，且axi mod nn，因此axi mod nR，所以aRR。,欧拉定理,-,又因aR中任意两个元素都不相同，否则axi mod n=axj mod n，由a与n互素知a在 mod n下有乘法逆元，得xi=xj。所以|aR|=|R|，得aR=R，所以 ， , ，,欧拉定理,由每一xi与n互素，知 与n互素， 在 mod n下有乘法逆元。 所以a(n)1 mod n。 (证毕）,欧拉定理,-,-,素性检验是指对给定的数检验其是否为素数。对于大数的素

20、性检验来说没有简单直接的方法，本节介绍一个概率检验法，为此需要以下引理。,1.4 素性检验,-,引理 如果p为大于2的素数，则方程x2 1(mod p)的解只有x1和x-1。 证明：由x21 mod p，有x2-10 mod p，(x+1)(x-1)0 mod p，因此p|(x+1)或p|(x-1)或 p|(x+1)且p|(x-1)。 若p|(x+1)且p|(x-1)，则存在两个整数k和j，使得x+1=kp，x-1=jp,两式相减得2=(k-j)p，为不可能结果。所以有p|(x+1)或p|(x-1)。 设p|(x+1)，则x+1=kp，因此x-1(mod p)。类似地可得 x1(mod p)。

21、（证毕）,1.4 素性检验,-,引理的逆否命题为：如果方程x21 mod p有一解x0-1,1，那么p不为素数。 例如： 考虑方程x21(mod 8)由Z8上模乘法的结果得121 mod 8, 321 mod 8, 521 mod 8, 721mod 8 又5-3 mod 8，7-1 mod 8，所以方程的解为1，-1，3，-3，可见8不是素数。,1.4 素性检验,-,下面介绍Miller-Rabin的素性概率检测法。首先将n-1表示为二进制形式bkbk-1b0，并给d赋初值1，则算法Witness(a,n)的核心部分如下： for i=k downto 0 doxd;d(dd) mod n;

22、if d=1 and(x1)and(xn-1)then return False;if bi=1 then d(da) mod nif d1 then return False;return True.,1.4 素性检验,-,此算法有两个输入参数，n是待检验的数，a是小于n的整数。如果算法的返回值为False，则n肯定不是素数，如果返回值为True，则n有可能是素数。 for循环结束后，有dan-1 mod n，由Fermat定理知，若n为素数，则d为1。因此若d1，则n不为素数，所以返回False。因为n-1-1 mod n，所以(x1)and(xn-1),指x21 (mod n)有不在-1

23、,1中的根，因此n不为素数，返回False。,1.4 素性检验,-,该算法有以下性质： 对s个不同的a，重复调用这一算法，只要有一次算法返回为False，就可肯定n不是素数。如果算法每次返回都为True，则n是素数的概率至少为1-2-s，因此对于足够大的s，就可以非常肯定地相信n为素数。,1.4 素性检验,-,欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。,1.5 欧几里得算法,-,1. 求最大公因子Euclid算法是基于下面一个

24、基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b, a mod b)。 证明：b是正整数，因此可将a表示为a=kb+rr mod b，a mod b=r,其中k为一整数，所以a mod b =a-kb。,1.5 欧几里得算法,设d是a，b的公因子，即d|a，d|b，所以d|kb。由d|a和d|kb得d|(a mod b)，因此d是b和a mod b的公因子。 所以得出a，b的公因子集合与b，a mod b的公因子集合相等，两个集合的最大值也相等。（证毕）,1.5 欧几里得算法,-,-,例如： gcd(55, 22)=gcd(22, 55 mod 22)= gcd(22,

25、11)=gcd(11, 0)=11。在求两个数的最大公因子时，可重复使用以上结论。例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=1。,1.5 欧几里得算法,-,Euclid算法就是用这种方法，因gcd(a, b)= gcd(|a|, |b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f d。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 欧几里得算法,-

26、,例： 求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. 求

27、乘法逆元 如果gcd(a, b)=1 ，则b在mod a下有乘法逆元（不妨设ba），即存在一x (xa)，使得bx1 mod a。推广的Euclid算法先求出gcd(a, b)，当gcd(a, b)=1时，则返回b的逆元。,1.5 欧几里得算法,-,Extended Euclid(f, d) （设 f d） 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

28、；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

29、 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 1

30、769=550。,1.5 欧几里得算法,-,中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。 例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是0和3，即x mod 20，x mod 53。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。,1.6 中国剩余定理,-,定理4.5（中国剩余定理） 设m1,m2,mk是两两互素的正整数， ，则一次同余方程组对模M有惟一解:其中ei满足,1.6 中国剩余定理,-,证明：设 ,i=1,2,k，由Mi的定义得Mi与mi

31、是互素的，可知Mi在模mi下有惟一的乘法逆元，即满足的ei是惟一的。,1.6 中国剩余定理,-,下面证明对i1,2,k，上述x满足ai(mod mi)x。注意到当ji时，mi|Mj，即Mj0(mod mi)。所以(Mjej mod mj) mod mi (Mj mod mi)(ej mod mj) mod mi) mod mi 0而(Mi(ei mod mi) mod mi(Miei) mod mi1所以x(mod mi)ai，即ai(mod mi)x,1.6 中国剩余定理,-,下面证明方程组的解是惟一的。设x是方程组的另一解，即xai(mod mi)(i=1,2,k)由xai(mod mi)

32、得x-x0(mod mi)，即mi|(x-x)。 再根据mi两两互素，有M|(x-x)，即x-x0(mod M)，所以x(mod M)= x(mod M)。 (证毕),1.6 中国剩余定理,-,中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,ak)表达。,1.6 中国剩余定理,-,例： 由以下方程组求x。解： M=2357=210，M1=105，M2=70，M3=42，M4=30,易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M-14 mod 74,所以x mod 210(10511+7012+4233+304

33、5) 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。现在考虑如下的一般形式:am1 mod n 如果a与n互素，则至少有一整数m（比如m=(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。,

34、1.7 离散对数,-,例如： a=7，n=19，则易求出717 mod 19,7211 mod 19,731 mod 19，即7在模19下的阶为3。 由于73+j=737j7j mod 19, 所以747 mod 19,7572 mod 19, , 即从74 mod 19开始所求的幂出现循环，循环周期为3，即循环周期等于元素的阶。,模下的整数幂,-,定理4.6 设a的阶为m，则ak1 mod n的充要条件是k为m的倍数。证明：设存在整数q，使得k=qm，则ak(am)q1 mod n。反之，假定ak1 mod n，令k=qm+r,其中0rm-1，那么ak(am)qarar1(mod n)与m是

35、阶矛盾。（证毕）,模下的整数幂,-,推论：a的阶m整除(n)。如果a的阶m等于(n)，则称a为n的本原根。如果a是n的本原根，则 a,a2,a(n)在mod n下互不相同且都与n互素。 特别地，如果a是素数p的本原根，则a,a2,ap-1在 mod p下都不相同。,模下的整数幂,-,例如：n=9，则(n)=6，考虑2在mod 9下的幂21 mod 92,22 mod 94 23 mod 98,24 mod 97，25 mod 95, 26 mod 91。即2的阶为(9)，所以2为9的本原根。,模下的整数幂,-,例如： n=19，a=3在mod 19下的幂分别为3，9，8，5，15，7，2，6，

36、18，16，10，11，14，4，12，17，13，1。即3的阶为18=(19)，所以3为19的本原根。,模下的整数幂,-,本原根不惟一。可验证除3外，19的本原根还有2，10，13，14，15。注意并非所有的整数都有本原根，只有以下形式的整数才有本原根： 2,4,p,2p 其中p为奇素数。,模下的整数幂,-,2. 指标一般对数的概念:指数函数y=ax(a0,a1)的逆函数称为以a为底x的对数，记为y=logax。对数函数有以下性质： loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设p是一素数，a是p的本原根，则a,a

37、2,ap-1产生出1到p-1之间的所有值，且每一值只出现一次。因此对任意b1,p-1，都存在惟一的i(1ip-1)，使得bai mod p。称i为模p下以a为底b的指标，记为i=inda,p(b)。,指标,-,指标有以下性质： inda,p(1)=0。 inda,p(a)=1。 分别由以下关系得出： a0 mod p=1 mod p=1,a1 mod p=a。以上假定模数p是素数，对于非素数也有类似的结论。,指标,-,例： 设p=9，则(p)=6，a=2是p的一个本原根，a的不同的幂为（模9下）201,212,224,238,247,255,261由此可得a的指数表如下所示。,指标,-,在讨论

38、指标的另两个性质时，需要利用如下结论： 若azaq mod p，其中a和p互素，则有zq mod (p)。证明：因a和p互素，所以a在模p下存在逆元a-1，在azaq mod p两边同乘以(a-1)q，得az-q1 mod p。由Euler定理a(p)1 mod p知存在一整数k，使得z-qk(p)，所以 zq mod (p)。,指标,-,由上述结论可得指标的以下两个性质： inda,p(xy)=inda,p(x)+inda,p(y) mod (p)。 inda,p(yr)=rinda,p(y) mod (p)。性质是性质的推广。从指标的以上性质可见，指标与对数的概念极为相似。,指标,-,性质

39、的证明：设由模运算的性质得：所以inda,p(xy)=inda,p(x)+inda,p(y) mod (p)（证毕）,指标,-,3. 离散对数 设p是素数，a是p的本原根，即a1,a2,ap-1在 mod p下产生1到p-1的所有值，所以对b1,p-1，有惟一的i1,p-1使得bai mod p。称i为模p下以a为底b的离散对数， 记为 ilogab(mod p)。,离散对数,当a、p、i已知时，用快速指数算法可比较容易地求出b，但如果已知a、b和p，求i则非常困难。目前已知的最快的求离散对数算法其时间复杂度为：所以当p很大时，该算法也是不可行的。,离散对数,-,-,设p是一素数，a小于p，称

40、a是p的平方剩余，如果方程 x2a (mod p)有解。否则称为非平方剩余。,1.8 平方剩余,求离散对数的shank算法,-,求5x mod 23=3m=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, 若x2a(mod n)有解, 则称a是模p的二次剩余; 若无解,

41、 则称a是模p的二次非剩余.二次剩余集合QRn二次非剩余集合QNRn.,-,-,容易证明，模p的平方剩余的个数为(p-1)/2，且与模p的非平方剩余的个数相等。如果a是模p的一个平方剩余，那么a恰有两个平方根，一个在0到(p-1)/2之间，另一个在(p-1)/2到(p-1)之间，且这两个平方根中的一个也是模p的平方剩余。,1.8 平方剩余,欧拉准则,定理 (欧拉准则)设p为一奇素数, p不能整除x, 则有: x属于QRp证明: （1）若存在y2x(mod p), （2）若 ，但y2x(mod p)无解 对任意1 i p-1, 总有一整数j, 使得: ij x(mod p). 由于y2x(mod

42、 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 p511 mod p=-1，所以5不是模23的平方剩余。,1.8 平方剩余,为了简化“x2a(mod p)有解”这一较长的说法, 今引人勒让德(Legendre)符号 ,其定义

43、如下:设p为奇素数, 且p不能整除a, 则: 当a是模户二次剩余; 当a是模p二次非剩余.例如, , 因为x23(mod 5)无解; ,因为1是模5的二次剩余.,-,勒让德符号,下面给出Legendre符号的三条简单而又重要的性质定理6.16 若ab(mod p), 则 若p不能整除a, 则 若p不能整除a与b, 则:,-,类似可证, 若 , ab(mod p),则 .显然, 若 , ab(mod p), 则由欧拉准则知: 故:,-,由于同余式两端只能是1或-1, 这两数对模p要同余, 只有相等就行, 故有:表明了,两个剩余的乘积是剩余;两个非剩余的乘积也是一剩余; 一个剩余和一个非剩余的乘积

44、是一非剩余.,-,若 其中, 是素数, 1in, 则有:因为 所以任给一整数a, 计算只需要计算出三种值: 其中q为奇素数.,-,对于每一奇素数p, 则有: 若p1(mod 4) 若p3(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, 则有:该定理是说, pq3(mod 4), 则二同余式:x2p(mod p), x2q(mod

45、 p)中一有解,一无解. 不然,则皆有解,或皆无解.,-,例. 验证 x285(mod 97)有解.证明: 若 则证明即完成. 因为 而97 1(mod 4), 故有二次互反定理知, 又由 ,而,-,当p5(mod 8)时, a(p-1)/4-1(mod p)时, a(p+3)/8为x2a(mod p)的解;,设 ,则有:当p3(mod 4)时, a(p-1)/4为x2a(mod p)的解.,当p5(mod 8)时, a(p-1)/41(mod p)时, a(p+3)/8为x2a(mod p)的解;,-,设p1(mod 8), 则同余式有x2a(mod p)解a(q+1)/2bte, 其中q满

46、足: p=2kq+1, q是奇数, te0是某个整数.证明: 由p1(mod 8), 可设p=2eq+1, e3, 2不能整除q, 由 得出:,-,于是,若,则,所以存在非负整数 使得,-,于是, 故有非负整数 使下式成立:,-,因为e是有限整数, 故必有一非负整数te使得:aqb2te1(mod p)于是得:aq+1b2tea(mod p)即:(a(q+1)/2bte)2a(mod p),-,例. 解 x285(mod 97),979612531,-,Shank算法,设p=2eq+1，,设g是G的生成元,有唯一的阶为2e的循环子群G，,存在整数r,-,g如何确定？,若,取,即可,-,k如何确定？,取,找最小的m,设,-,找最小的m1,取,重复过程，知道找到,-,例. 解 x285(mod 97),979612531,-,