密码学中的数论基础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

2、,也称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)。

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

4、|b可得：对每一素数p,apbp。这是因为pk只能被pj(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=223152；18=2132gcd(1

5、8,300)=213150=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。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 是唯一的公因子 为了规范事业单位聘用关系

6、，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益素数与不可约多项式素数:只有因子 1 和自身1 是一个平凡素数例 2,3,5,7 是素数,4,6,8,9,10 不是素多项式或不可约多项式irreducible:不可写成其他因式的乘积 x2+x=x x+1 是非不可约多项式;x3+x+1 是不可约多项式为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益一些素数200 以内的素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

7、 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，得商为q，余数为r，则a=qn+r,0rn,其中x为小于或等于x的最大整数。用a mod n表示余数r，则

8、 。如果(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

9、,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+rb mod n=(ra+rb)mod n=(a mod n)+(b mod n)mod n （证毕）性质、的证明类似。1.

10、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的同的同余类余类集合。其上的模运算有以下性质

11、：交换律 (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 n1.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的

12、加法逆元得到。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，则a在Zn中有乘法逆元。证明：首先证明a与Zn中任意两个不相同的数b、c（

13、不妨设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的乘法逆元。

14、记为x=a-1。（证毕）1.2 模运算 设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律加法可约律，可有以下乘法可约律乘法可约律：如果(ab)(ac)mod n且a有乘法逆元，那么对(ab)(ac)mod n两边同乘以a-1，即得bc mod n1.2 模运算-为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益模算式除法取余运算 同余(congruence)for a=b mod n 如果a,b 除以n,余数相同eg.100=34 mod 11 b 叫做a模n的剩余 通常 0=b=n-1 eg.-1

15、2mod7=-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 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 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作

16、人员聘用制度，保障用人单位和职工的合法权益模算术运算加法加法 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 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员

17、聘用制度，保障用人单位和职工的合法权益模递归运算模递归运算是“模除求余”例.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互素，则a(n)1 mod n。1.3 费尔玛定理和欧拉定理-费尔玛定理证明：当gcd(a

18、,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 因此 (p-1)!ap-1(p-1)!mod p 由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可

19、约律得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，其中不与n互素的数有3类，A=p,2p,(q-1)p，B=q,2q,(p-1)q,C=0，且AB=，否则ip=jq，其中1iq-1，1jp-1,

20、则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=ax1 mod n,ax2 mod n,ax(n)mod n，对aR中任一元素axi mod n，因a与n互素，x1与n互素，所以axi与n互素，且axi m

21、od 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

22、+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.(

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

24、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 欧几里得算法-中国剩余定理中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数

25、的同余类集，就可重构这个数。例如：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是互素的，可知Mi在模mi下有惟一的乘法逆元，即满足的ei是惟一的。1.6 中国剩余定理-下面证明对i1,2,k，上述x满足ai(mod mi

26、)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)x1.6 中国剩余定理-下面证明方程组的解是惟一的。设x是方程组的另一解，即xai(mod mi)(i=1,2,k)由xai(mod mi)得x-x0(mod mi)，即mi|(x-x)。再根据mi两两互素，有M|(x-x)，即x-x0(mod M)，所以x(mod M)=x(mod M)。(证毕)1.

27、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+3045)mod 210173，或写成x173 mod 210。1.6 中国剩余定理-例：将973 mod 1813由模数分别为37和49的两个数表示。解：

28、取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的阶。1.7 离散对数-例如：a=7，n=19，则易求出717 mod 19,7211 mod 19,731 mod 19，即7在模19下的阶为3。由于73+j=737j7j

29、 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,其中00,a1)的逆函数称为以a为底x的对数，记为y=logax。对数函数有以下性质：loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设p是一素数，a是p的本原根，则a,a2,

30、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的指数表如下所示。指标-在讨论指标的另两个性质时，需要利用如下

31、结论：若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)。性质是性质的推广。从指标的以上性质可见，指标与对数的概念极为相似。指标-性质的证明：设由模运算的性质得：所以inda,p(xy)=inda

32、,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很大时，该算法也是不可行的。离散对数

33、 设p是一素数，a小于p，称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 mo

34、d 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的二次剩余的二次剩余;若无解若无解,则称则称a是模是模p的二的二次非剩余次非剩余.二次剩余集合二次剩余集合QRn二次非剩余集合二次非剩余集合QNRn.容易证明，模p的平方剩余的个数为(p-1)/2，且与模p的非平方剩余的个数相等。如果a是模

35、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 p)无解.故ij.因此,

36、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)有解”这一较长的说

37、法,今引人勒让德(Legendre)符号 ,其定义如下:设p为奇素数,且p不能整除a,则:当a是模户二次剩余;当a是模p二次非剩余.例如,因为x23(mod 5)无解;,因为1是模5的二次剩余.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益勒让德符号下面给出Legendre符号的三条简单而又重要的性质定理定理6.16 若若a b(mod p),则则 若若p不能整除不能整除a,则则 若若p不能整除不能整除a与与b,则则:为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的

38、合法权益类似可证,若 ,ab(mod p),则 .显然,若 ,ab(mod p),则由欧拉准则知:故:为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益由于同余式两端只能是1或-1,这两数对模p要同余,只有相等就行,故有:表明了,两个剩余的乘积是剩余;两个非剩余的乘积也是一剩余;一个剩余和一个非剩余的乘积是一非剩余.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益若 其中,是素数,1in,则有:因为 所以任给一整数a,计算只需要计算出三种值:其中q为奇素数.为了

39、规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对于每一奇素数对于每一奇素数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是奇

40、素数是奇素数,则则为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益(高斯二次互反定理高斯二次互反定理)若若p和和q是二奇素数是二奇素数,且且pq,则有则有:该定理是说,pq3(mod 4),则二同余式:x2p(mod p),x2q(mod p)中一有解,一无解.不然,则皆有解,或皆无解.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例.验证 x285(mod 97)有解.证明证明:若 则证明即完成.因为 而97 1(mod 4),故有二次互反定理知,又由

41、,而 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 当当p 5(mod 8)时时,a(p-1)/4-1(mod p)时时,a(p+3)/8为为x2 a(mod p)的解的解;设设 ,则有则有:当当p 3(mod 4)时时,a(p-1)/4为为x2 a(mod p)的解的解.当当p 5(mod 8)时时,a(p-1)/4 1(mod p)时时,a(p+3)/8为为x2 a(mod p)的解的解;为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益设设p 1(mo

42、d 8),则同余式有则同余式有x2 a(mod p)解解a(q+1)/2bte,其中其中q满足满足:p=2kq+1,q是奇数是奇数,te0是某个整数是某个整数.证明证明:由p1(mod 8),可设p=2eq+1,e3,2不能整除q,由 得出:为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益于是,若则所以存在非负整数 使得为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益于是,故有非负整数 使下式成立:为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的

43、事业单位工作人员聘用制度，保障用人单位和职工的合法权益因为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