第七章-平方剩余课件.ppt

《第七章-平方剩余课件.ppt》由会员分享，可在线阅读，更多相关《第七章-平方剩余课件.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章第七章电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章第七章 平方剩余平方剩余7.1平方剩余（平方剩余（熟练熟练）7.2勒让德符号（勒让德符号（掌握掌握）7.3雅可比符号（雅可比符号（掌握掌握）电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.1 平方平方剩余剩余定义定义7.1.1设设p是奇素数，即大于是奇素数，即大于2的素数，的素数，如果二次同余式如果二次同余

2、式x2 a(mod p)，(a，p)=1 (1)有解，则有解，则a称为模称为模p的的平方剩余平方剩余，否则否则a成为成为模模p的的平方非剩余平方非剩余 之所以规定之所以规定p是大于是大于2的素数，是因为的素数，是因为p=2时解二次同余式时解二次同余式(1)非常容易在有些书籍非常容易在有些书籍中，平方剩余和平方非剩余又分别称为中，平方剩余和平方非剩余又分别称为二二次剩余次剩余和和二次非剩余二次非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余例例7.1.1求出求出p=5，7时的平方剩余和平方非剩余时的平方剩余和平方非剩

3、余解解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的平方非的平方非剩余剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学

4、电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余于是模于是模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 时这显然是不可能的时这显然是不可能的，故证得，故证得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩

5、余平方平方剩余剩余所以在模所以在模p的简化剩余系中，有的简化剩余系中，有 个平方剩余，个平方剩余，同时有同时有 个平方非剩余个平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余 以后我们求模以后我们求模p的平方剩余时，就可以只计算下列的平方剩余时，就可以只计算下列数了：数了：12，22，电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余定

6、理定理7.1.2（欧拉判别法欧拉判别法）设）设p是奇素数，是奇素数，(a，p)=1a是模是模p平方剩余的充分必要条件是平方剩余的充分必要条件是a是模是模p平方非剩余的充分必要条件是平方非剩余的充分必要条件是电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余证明定理第证明定理第1部分证明：部分证明：必要条件证明：必要条件证明：因为因为a是模是模p的平方剩余，则存在的平方剩余，则存在b,使使 b2 a(mod p)充分条件证明：充分条件证明：由于由于,由定理由定理6.4.4，同余式，同余式电子科技大学电子科技大学 计算机科学与

7、工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余定理第定理第2部分证明：部分证明：对于任意对于任意a GF(p)*，有，有ap 1 1(mod p)，即即 ap 1 1 0(mod p)，由于由于p是素数，则是素数，则即即电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余例例7.

8、1.31）判断）判断3是不是模是不是模17的平方剩余？的平方剩余？解因为解因为32 9(mod 17)，34 81 4(mod 17)，所以所以3是模是模17的的平方非剩余平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方平方剩余剩余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的平方剩余的平方剩余电子科技大学电

9、子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒让德符号勒让德符号2）如果）如果a b(mod p)，则，则3）4）如果）如果(a，p)=1，则，则5）电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒让德符号勒让德符号性质性质5证明：证明：因为因为 于是于是电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒让德符号勒让德符号 由

10、于由于p是奇素数，是奇素数，p 2，而勒让德符号只能取值，而勒让德符号只能取值0，1，所以上式中，所以上式中k只可能等于只可能等于0，所以我们有，所以我们有电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余定理定理该结论可以作为勒让德符号的该结论可以作为勒让德符号的第第6项性质项性质定理定理7.2.2（二次互反律）如果（二次互反律）如果p，q都是奇素数，都是奇素数，(p，q)=1，则，则电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律勒让德符号性质勒让德符号性质

11、7：证明：分别把证明：分别把p 1(mod 8)，p 3(mod 8)，代入代入 式中便得式中便得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律（因为（因为563 2(mod11)）则则故故286是模是模563的平方非剩余的平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律例例7.2.2判断判断x2=137(mod 227)是

12、否有解是否有解解解227是奇素数，又是奇素数，又137 90 2 32 5(mod227)，则，则而而电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律故故原同余式无解原同余式无解电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号1）2）如果）如果a b(mod m)，则，则3）如果）如果(a，m)=1，则，则4）5）6）7）电子科技大学电

13、子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余证明性质证明性质6证明：证明：现在只需证明现在只需证明而而故得证故得证，故性质6证得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号定理定理7.3.1如果如果m，n都是大于都是大于1的奇数，则的奇数，则证明证明如果如果(m，n)1，得到，得到定理成立现在假设定理成立现在假设(m，n)=1设设n=q1q2qs是是n的素数分解

14、，则的素数分解，则电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号我们有我们有故故电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余例例1判断判断339是否模是否模1979的平方剩余的平方剩余解解1979是奇素数，所以该例是求勒让德符号是奇素数，所以该例是求勒让德符号 而此时勒让德符号与雅可比符号是一致的，所以我而此时勒让德符号与雅可比符号是一致的，所以我们

15、求们求339对对1979的雅可比符号：的雅可比符号：因为因为1979=284 mod(339)电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余339=55 mod(71)因为因为71=16 mod(55)电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号 所以所以339对对1979的勒让德符号也等于的勒让德符号也等于 1，故，故339是模是模1979的平方非剩余的平方非剩余需要注意需要注意:电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余作业作业12610(1)11(1)14(1)18(1)19(1)