第七章-平方剩余演示文稿.ppt

电子科技大学 计算机科学与工程学院 UESTC Press 第七章 平方剩余 电子科技大学 计算机科学与工程学院 UESTC Press 《信息安全数学基础》 前言 第七章 平方剩余 第七章 平方剩余 7.1　平方剩余（熟练） 7.2　勒让德符号（掌握） 7.3　雅可比符号（掌握） 7.1 平方剩余 定义7.1.1　设p是奇素数，即大于2的素数，如果二次同余式 x2 ? a (mod p)，(a，p) = 1 (1) 有解，则a称为模p的平方剩余，否则a成为模p的平方非剩余． 之所以规定p是大于2的素数，是因为p = 2时解二次同余式(1)非常容易．在有些书籍中，平方剩余和平方非剩余又分别称为二次剩余和二次非剩余． 平方剩余 例7.1.1　求出p = 5，7时的平方剩余和平方非剩余． 解　p = 5时，因为 12 ? 1 (mod 5)，22 ? 4 (mod 5)， 32 ? 4 (mod 5)，42 ? 1 (mod 5)， 所以1，4是模5的平方剩余，而2，3是模5的平方非剩余． p = 7时，因为 12 ? 1 (mod 7)，22 ? 4 (mod 7)， 32 ? 2 (mod 7)，42 ? 2 (mod 7)， 52 ? 4 (mod 7)，62 ? 1 (mod 7)， 所以1，2，4是模7的平方剩余，而3，5，6是模7的平方非剩余． 平方剩余 定理7.1.1　设p是奇素数．在模p的简化剩余系中，有 个平方剩余， 个平方非剩余． 证明　取模p的最小绝对简化剩余系 则模p的全部平方剩余为 由于 (?a)2 ? a2 (mod p) 平方剩余 于是模p的全部平方剩余为 现在证明这个 平方剩余两两不同，用反证法． 假设 i2 ? j2 (mod p)，i?j，1?i，j? ， 则 (i + j)(i ?j) ? 0 (mod p)， p?(i + j)(i?j)， 因为p是素数，于是 p?(i + j)或p?(i?j)， 当i?j，1?i，j? 时这显然是不可能的，故证得． 平方剩余 所以在模p的简化剩余系中，有 个平方剩余，同时有 个平方非剩余． 平方剩余 以后我们求模p的平方剩余时，就可以只计算下列数了： 12，22，…， ． 平方剩余 例7.1.2　求出p = 11，17时的平方剩余和平方非剩余． 解　p = 11时： 12 ? 1 (mod 11)，22 ? 4 (mod 11)，32 ? 9 (mod 11)，42 ? 5 (mod 11)，52 ? 3 (mod 11)， 所以1，3，4，5，9是模11的平方剩余，而2，6，7，8，10是模11的平方非剩余． p = 17时： 12 ? 1 (mod 17)，22 ? 4 (mod 17)，32 ? 9 (mod 17)，42 ? 16 (mod 17)，52 ? 8 (mod 17)，62 ? 2 (mod 17)，72 ? 15 (mod 17)，82 ? 13 (mod 17)， 所以1，2，4，8，9，13，15，16是模17的平方剩余，而3，5，6，7，10，11，12，14是模17的平方非剩余． 平方剩余 定理7.1.2　（欧拉判别法）设p是奇素数，(a，p) = 1． a是模p平方剩余的充分必要条件是 a是模p平方非剩余的充分必要条件是 平方剩余 由定理的第1部分，a是模p平方剩余的充分必要条件是 那么a是模p平方非剩余的充分必要条件就是 定理证毕． 平方剩余 例7.1.3　1）判断3是不是模17的平方剩余？ 解　因为 32 ? 9 (mod 17)， 34 ? 81 ? ?4 (mod 17)， 所以3是模17的平方非剩余． 平方剩余 2）7是不是模29的平方剩余？ 解　因为 72 = 49 ? ?9 (mod 29)， 74 ? (?9)2 ? 81 ? ?6 (mod 29)， 78 ? (?6)2 ? 36 ? 7 (mod 29)， = 714 =78?74?72 ? 7?(?6)?( ?9) ? 1 (mod 29)， 所以7是模29的平方剩余． 7.2 勒让德符号 定义7.2.1　设p是奇素数，a是整数．勒让德（Legendre）符号定义如下： 由欧拉判别法我们立即得到下面的定理． 定理7.2.1勒让德符号 具有下列性质： 勒让德符号 2）如果a ? b (mod p)，则