第五讲-二次剩余_第1页
第五讲-二次剩余_第2页
第五讲-二次剩余_第3页
第五讲-二次剩余_第4页
第五讲-二次剩余_第5页
已阅读5页，还剩16页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第5讲二次剩余教师：李艳俊本讲内容一、二次剩余的概念二、模为奇素数的平方剩余与平方非剩余三、勒让德符号四、雅可比符号五、小结一、二次剩余的概念二次同余式的一般形式是其中m是正整数，。上式等价于同余式

定义1设m是正整数，若同余式有解，则a叫做模m的平方剩余(或二次剩余)；否则a叫做模m的平方非剩余(或二次非剩余)。例1分别求出模11，12的二次剩余和二次非剩余。解：模11的二次剩余是：1，3，4，5，9；二次非剩余是：2，6，7，8，10。模12的二次剩余是：1；二次非剩余是：5，7，11。例2求满足同余式的所有的点。解：模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。对，分别求出对应的的值为无解无解二、模为奇素数的平方剩余与平方非剩余

定理1(欧拉判别条件)设p是奇素数，，则

(1)a是模p的平方剩余的充分必要条件是

(2)a是模p的平方非剩余的充分必要条件是当a是模p的平方剩余时，同余式恰有两解。解:例判断137是否为模227平方剩余。

定理2设p是奇素数，则模p的简化剩余系中平方剩余与平方非剩余的个数各为，且个平方剩余与序列中的一个数同余，且仅与一个数同余。所以137是模227平方非剩余。三、勒让德符号由此定义，欧拉判别法则可以表示成如下形式：

定义设p是素数，定义勒让德符号如下：定理设p是奇素数，则对任意整数a，有设p是奇素数，则勒让德符号有如下性质：(2)，进一步，若，则；(3)，进一步，若，则，若，则；(1)，；(5)若是互素的奇素数，则。(4)；例1计算如下勒让德符号的值。(1)

(2)

(3)m是否为素数q=0q=1q=-1q=2out:01停止否是，计算nmodm=q返回为奇数；为偶数。例2

判断同余式是否有解？有解时，求出其解数。例3判断同余式是否有解？有解时，求出其解数。

注意：雅可比符号为1时，不能判断a是否为模m的平方剩余。例如四、雅可比符号

定义设是奇素数的乘积。对任意整数，定义雅可比(Jacobi)符号为

因为，而同余式组的每个同余式都无解，所以3是模119的平方非剩余。当m为奇素数时，则上式为勒让德符号。

如果，则；设m是奇数，则雅可比符号有以下性质：

，如果，则；(3)(2)；(1)，(4)(5)设m,n都是奇数，则。例判断同余式是否有解？解：不用考虑563是否为素数，直接计算雅可比符号:所以同余式无解。当n是合数的时候，若（a/n）=1，则a不一定是模n的二次剩余。定义则有。集合中的数称为模n的伪二次剩余。124581011131617192014164116161416411-11-1-11-111-11-1111-11-11-11-1-1-11-111-1-1-1-111-11例：a结论：猜想二次剩余问题的难度与因子分解难度相当。定理3.12若n=pq，且n的素因子p和q已知，则整数a为模n的二次剩余，当且仅当五、小结1、m是正整数a是m的二次剩余。2、欧拉判别条件p是奇素

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论