第九章课件 二次剩余

1、二次剩余二次剩余本讲内容本讲内容二次剩余的概念二次剩余的概念模为奇素数的二次剩余与二次非剩余模为奇素数的二次剩余与二次非剩余 勒让德符号勒让德符号 RabinRabin公钥密码算法公钥密码算法二次剩余的概念二次剩余的概念二次同余式的一般形式是二次同余式的一般形式是)(mod02mcbxax)(mod0ma 其中其中m是正整数，是正整数， 。上式等价于同余式上式等价于同余式2(mod)ydm22,4yaxb dbac)(mod2max1),(ma设设m是大于是大于1的整数，若同余式的整数，若同余式有解，则有解，则a叫做模叫做模m的二次剩余；否则的二次剩余；否则a叫做模叫做模m的二次非的二次非剩余

2、。剩余。例：求满足同余式例：求满足同余式 的所有的点。的所有的点。 )7(mod232xxy模模7的二次剩余是：的二次剩余是：1，2，4；二次非剩余是：；二次非剩余是：3，5，6。 对对 ，分别求出，分别求出 对应的的值为对应的的值为 )7(mod6 , 5 , 4 , 3 , 2 , 1 , 0 xy)7(mod0 x)7(mod22y)7(mod4 , 3y)7(mod1x)7(mod42y)7(mod5 , 2y)7(mod3x)7(mod42y)7(mod5 , 2y)7(mod4x)7(mod02y)7(mod0y)7(mod6x)7(mod02y)7(mod0y)7(mod2x)7

3、(mod52y无解无解)7(mod5x)7(mod62y无解无解二次剩余的分布二次剩余的分布 设设p是奇素数，则模是奇素数，则模p的简化剩余系中二次剩的简化剩余系中二次剩余与二次非剩余的个数各为余与二次非剩余的个数各为 ，且，且 个二次剩余与个二次剩余与序列序列中的一个数同余，且仅与一个数同余。中的一个数同余，且仅与一个数同余。21p21p222)21( ,2 ,1p二次剩余的分布规律二次剩余的分布规律二次剩余的分布规律的证明二次剩余的分布规律的证明n取模p的绝对值最小缩系来讨论 -(p-1)/2, -(p-1)/2+1, , -1, 1, , (p-1)/2-1, (p-1)/2na是模p的

4、二次剩余当且仅当a -(p-1)/22, -(p-1)/2+12, , (-1)2, 12, , (p-1)/2-12, (p-1)/22(mod p)n而(-i)2=i2(mod p)，所以a是模p的二次剩余当且仅当 a 12, , (p-1)/2-12, (p-1)/22(mod p) n又因为1ij (p-1)/2时， i2 ! j2(mod p)n所以模p的全部二次剩余即 12, , (p-1)/2-12, (p-1)/22(mod p) 共有(p-1)/2个，所以模p的二次非剩余共有(p-1)- (p-1)/2= (p-1)/2个欧拉判别条件欧拉判别条件欧拉判别条件欧拉判别条件 设设

5、p是奇素数，是奇素数，(a, p) = 1，则，则 (1) a是模是模p的平方剩余的充分必要条件是的平方剩余的充分必要条件是 (2) a是模是模p的平方非剩余的充分必要条件是的平方非剩余的充分必要条件是当当a是模是模p的平方剩余时，同余式的平方剩余时，同余式 恰有两解。恰有两解。)(mod121pap)(mod121pap)(mod2pax 欧拉判别条件的证明欧拉判别条件的证明n先来证明结论(1)的必要性，a是模p的二次剩余，则必有x0，使得 x02 a(mod p)成立，因而 x0 (p-1) a(p-1)/2(mod p)因为(a, p) = 1，所以(x0 , p) = 1，所以 x0

6、(p-1) 1(mod p)所以 a (p-1)/2 1(mod p)欧拉判别条件的证明欧拉判别条件的证明n再来证明结论(1)的充分性，用反证法，假设满足 a (p-1)/2 1 (mod p)的a不是模p的二次剩余n考虑线性同余方程sx a(mod p)，当s从模p的绝对值最小缩系 -(p-1)/2, -(p-1)/2+1, , -1, 1, , (p-1)/2-1, (p-1)/2 中取值时，方程sx a(mod p) 必有唯一解n亦即s取模p的绝对值最小缩系中的每个元素i，必有唯一的x=xi属于模p的绝对值最小缩系，使得sx a(mod p) 成立，若a不是模p的二次剩余，则ixi，这样

7、模p的绝对值最小缩系中的p-1个数可以按两两配对相乘，得到 (p-1)! a (p-1)/2(mod p)n由威尔逊定理(p-1)! -1(mod p)，所以有a (p-1)/2 -1 (mod p)，这与条件a (p-1)/2 1 (mod p)矛盾n所以必定存在一个i，使得i=xi ，即a是模p的二次剩余欧拉判别条件的证明欧拉判别条件的证明n最后来证明(2)成立，只需证明 a(p-1)/2 1(mod p)和a(p-1)/2 -1(mod p)有且仅有一个成立即可n由欧拉定理 a(p-1) 1(mod p) 所以 (a(p-1)/2-1) (a(p-1)/2+1) 0(mod p)而p2，

8、且有 (a(p-1)/2-1, a(p-1)/2+1)|2于是 a(p-1)/2 1 (mod p)和a(p-1)/2 -1(mod p)有且仅有一个成立欧拉判别条件例题欧拉判别条件例题欧拉判别条件的推论欧拉判别条件的推论勒让德符号勒让德符号由此定义，欧拉判别法则可以表示成如下形式：由此定义，欧拉判别法则可以表示成如下形式： , 0, 1, 1paappapa|若的平方非剩余是模若的平方剩余是模若 定义定义 设设p是素数，定义勒让德符号如下：是素数，定义勒让德符号如下：设设p是奇素数，则对任意整数是奇素数，则对任意整数a，有，有 )(mod21papap设设p是奇素数，则勒让德符号有如下性质：

9、是奇素数，则勒让德符号有如下性质： (2) ，进一步，若，进一步，若 ，则，则 ；pappa)(mod pba pbpa(3) ，进一步，若，进一步，若 ，则，则 ， 若若 ，则，则 ；pbpapab1),(pa12pa1),( pa02pa11p21) 1(1 pp(1) ， ；勒让德符号勒让德符号勒让德符号勒让德符号高斯引理高斯引理高斯引理高斯引理二次互反律二次互反律二次互反律二次互反律华罗庚对高斯二次互反律的评价 设设p是奇素数，则勒让德符号有如下性质：是奇素数，则勒让德符号有如下性质： (2) ，进一步，若，进一步，若 ，则，则 ；pappa)(mod pba pbpa(3) ，进一步

10、，若，进一步，若 ，则，则 ， 若若 ，则，则 ；pbpapab1),(pa12pa1),( pa02pa11p21) 1(1 pp(1) ， ；qp,1122( 1)pqqppq (5) 若若 是互素的奇素数，则是互素的奇素数，则 。 812) 1(2pp(4) ；勒让德符号勒让德符号若p, q为奇素数nx2 -1(mod p)有解p 1(mod 4)nx2 2(mod p)有解p 1(mod 8)n若p 1(mod 4)或q 1(mod 4)则 x2 q(mod p)有解 x2 p(mod q)有解n若p 3(mod 4)且q 3(mod 4)则 x2 q(mod p)有解 x2 p(mo

11、d q)无解 x2 p(mod q)有解 x2 q(mod p)无解例例 计算如下勒让德符号的值。计算如下勒让德符号的值。 ,322,171732271372003911(1) (2) (3) 勒让德符号勒让德符号nmm是否为素数是否为素数q=1q=-1q=0q=2out:01停止停止否否是，计算是，计算n (mod m)=q218( 1)m 12( 1)m返回返回1212rkkkrqppp121111()222212( 1)ipppmimmmpppikkk,21riikkk,21为奇数为奇数为偶数为偶数勒让德符号勒让德符号二次剩余根的实际求法二次剩余根的实际求法n华罗庚的观点p=3(mod

12、4)时二次剩余根的实际求法时二次剩余根的实际求法n若p=3(mod 4)，且x2=a(mod p)有解，求其解可考虑 a(p-1)/21(mod p)两边同乘a，得 a(p+1)/2a (mod p)即 (a(p+1)/4 ) 21(mod p)n所以a(p+1)/4(mod p)即x2=a(mod p)的两个解1 判断同余方程判断同余方程21(mod307)x 是否有解？有解时，求出其解数。是否有解？有解时，求出其解数。2 判断同余方程判断同余方程230(mod419)x 是否有解？有解时，求出其解数。是否有解？有解时，求出其解数。 勒让德符号（作业）勒让德符号（作业）3 求解同余方程求解同

13、余方程22(mod23)x Rabin密码体制密码体制n对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解n但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识nRabin密码体制已被证明对该体制的破译与分解大整数一样困难Rabin密码体制密码体制1.密钥生成随机选择两个大素数p、q，满足 pq3 (mod 4)计算n=pq。以n作为公开钥，p、q作为秘密钥2.加密 cm2 (mod n) 其中m是明文，c是对应的密文Rabin密码体制密码体制3.解密即解方程x2c (mod n)，该方程等价于解方程组由于pq3 (mod 4)，设t=c(p

14、+1)/4 ，这两个方程各自有两个解，即 xt (mod p), x-t (mod p) xt (mod q), x-t (mod q)经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文，可在m中加入某些信息，如发送者的身份号、接收者的身份号、日期、时间等22modmodxcpxcqmod ,mod ,mod ,modmod ,mod ,mod ,modxtpxtpxtpxtpxtqxtqxtqxtq Rabin密码体制的例子密码体制的例子n设明文m按以下式加密：cm2 (mod 77)，如果密文c为23，求明文先求23对模7和模11的平方根，因为 7113 mod 4所以，23(7+1)/4 2324(mod 7) 23(11+1)/4 2331(mod 11)用中国剩余定理计算明文的可能取值为 10，32，45，67 小结小结)(mod2max 1),(ma1、m是正整数是正整数方程有解称方程有解称a是是m的二次剩余。的二次剩余。2、欧拉判别条件、欧拉判别条件p是奇素数是奇素数( , )1a p 121(mo