第九章课件-二次剩余.ppt

二次剩余本讲内容二次剩余的概念模为奇素数的二次剩余与二次非剩余 勒让德符号 Rabin公钥密码算法二次剩余的概念二次同余式的一般形式是其中m是正整数， 上式等价于同余式设m是大于1的整数，若同余式有解，则a叫做模m的二次剩余；否则a叫做模m的二次非剩余例：求满满足同余式 的所有的点 模7的二次剩余是：1，2，4；二次非剩余是：3，5，6 对 ，分别求出 对应的的值为 无解无解二次剩余的分布 设p是奇素数，则模p的简化剩余系中二次剩余与二次非剩余的个数各为 ，且 个二次剩余与序列中的一个数同余，且仅与一个数同余二次剩余的分布规律二次剩余的分布规律的证明n取模p的绝对值最小缩系来讨论-(p-1)/2, -(p-1)/2+1, …, -1, 1, …, (p-1)/2-1, (p-1)/2na是模p的二次剩余当且仅当 a ≡ [-(p-1)/2]2, [-(p-1)/2+1]2, …, (-1)2, 12, …, [(p-1)/2-1]2, [(p-1)/2]2(mod p)n而(-i)2=i2(mod p)，所以a是模p的二次剩余当且仅当a ≡ 12, …, [(p-1)/2-1]2, [(p-1)/2]2(mod p) n又因为1≤i两两配对相乘，得到(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) 而p>2，且有(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) 有且仅有一个成立欧拉判别条件例题欧拉判别条件的推论勒让德符号由此定义，欧拉判别法则可以表示成如下形式： 定义 设p是素数，定义勒让德符号如下：设p是奇素数，则对任意整数a，有 设p是奇素数，则勒让德符号有如下性质： (2) ，进一步，若 ，则 ；(3) ，进一步，若 ，则 ，若 ，则 ；(1) ， ；勒让德符号勒让德符号高斯引理高斯引理二次互反律二次互反律华罗庚对高斯二次互反律的评价 设p是奇素数，则勒让德符号有如下性质： (2) ，进一步，若 ，则 ；(3) ，进一步，若 ，则 ，若 ，则 ；(1) ， ；(5) 若 是互素的奇素数，则 。

(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(mod q)无解x2 ≡ p(mod q)有解 x2 ≡ q(mod p)无解例 计算如下勒让德符号的值 (1) (2) (3) 勒让德符号m是否为素数q=1q=-1q=0q=2out:01停止否是，计算n (mod m)=q返回为奇数为偶数勒让德符号二次剩余根的实际求法n华罗庚的观点p=3(mod 4)时二次剩余根的实际求法n若p=3(mod 4)，且x2=a(mod p)有解，求其解 可考虑a(p-1)/2≡1(mod p) 两边同乘a，得a(p+1)/2≡a (mod p) 即(a(p+1)/4 ) 2≡1(mod p)n所以±a(p+1)/4(mod p)即x2=a(mod p)的两个解1 判断同余方程是否有解？有解时，求出其解数。

2 判断同余方程 是否有解？有解时时，求出其解数 勒让德符号（作业）3 求解同余方程Rabin密码体制n对RSA密码体制，n被分解成功，该体制便 被破译，即破译RSA的难度不超过大整数的 分解n但还不能证明破译RSA和分解大整数是等价 的，虽然这一结论已得到普遍共识nRabin密码体制已被证明对该体制的破译与 分解大整数一样困难Rabin密码体制1.密钥生成 随机选择两个大素数p、q，满足p≡q≡3 (mod 4) 计算n=pq以n作为公开钥，p、q作为秘密钥1.加密c≡m2 (mod n)其中m是明文，c是对应的密文Rabin密码体制3.解密 即解方程x2≡c (mod n)，该方程等价于解方程组由于p≡q≡3 (mod 4)，设t=c(p+1)/4 ，这两个方程各自有两个解，即x≡t (mod p), x≡-t (mod p)x≡t (mod q), x≡-t (mod q) 经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应 的明文不惟一为了有效地确定明文，可在m中加入某些信息，如发 送者的身份号、接收者的身份号、日期、时间等Rabin密码体制的例子n设明文m按以下式加密：c≡m2 (mod 77)，如 果密文c为23，求明文¨先求23对模7和模11的平方根，因为7≡11≡3 mod 4¨所以，23(7+1)/4 ≡232≡4(mod 7)23(11+1)/4 ≡233≡1(mod 11)¨用中国剩余定理计算明文的可能取值为10，32，45，67小结1、m是正整数方程有解称a是m的二次剩余 。

2、欧拉判别条件p是奇素数3、勒让德符号的定义 设p是素数，定义如下：参考资料n勒让德符号计算器 http://math.fau.edu/richman/jacobi.htmn二次互反律的233个证明 http://www.rzuser.uni- heidelberg.de/~hb3/rchrono.html。