ImageVerifierCode 换一换
格式:PPT , 页数:46 ,大小:670.51KB ,
文档编号:3524152      下载积分:25 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-3524152.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(三亚风情)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(第五章-原根与指标-优质课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

第五章-原根与指标-优质课件.ppt

1、第五章第五章 原根与指数原根与指数PRIMITIVE ROOT学习目标v 掌握平方剩余与平方非剩余,v 能够算勒让德符号和雅可比符号,能够使用二次互反定律课程内容的设置v 平方剩余与平方非剩余v 勒让德符号v 二次互反定律v 雅可比符号5.0 5.0 问题的引入问题的引入本章围绕的是解高阶方程 xk a(mod m)主要利用的是欧拉定理 a (m)1(mod m)5.1 5.1 阶与原根阶与原根对xk 1(mod m),(a,m)=1,肯定有解,但最小解?定义5.1.1 n设 ,m 1,(a,m)=1,则使 a r 1(mod m)(1)成立的最小的正整数r,称为a对模m的阶,记为ordm(a

2、),在不致误会的情况下,简记为ord(a)。n例如:ordm(1)=1,ord2(-1)=1,ordm(-1)=1(m2),ord17(3)=16n注意!如果(a,m)1,则此时ordm(a)=0,以后,在谈到a对模m的指数时,总假定m 1,(a,m)=1 书上将此称为指数,阶更通用 ordm(a)等同的符号是 m(a),(a)Zma,5.1 5.1 阶与原根阶与原根模10的指数表 a1379ord10(a)1442a123456ord7(a136362模7的指数表 5.1 5.1 阶与原根阶与原根定理5.1.1 阶的基本性质 a n 1(mod m)的充要条件是ordm(a)|n 分析:设n

3、=ordm(a)q+r,0r ordm(a),q,rZ则:a n a ord(a)q+r a r 1(mod m),因为ordm(a)最小,所以r=0 推论:ordm(a)|(m)若ordm(a)=(m)称a是模m的原根(也写作元根)若a b(mod m),(a,m)=1,则ordm(a)=ordm(b)分析:a ord(a)b ord(b)a ord(b)b ord(a)1(mod m),所以ordm(a)|ordm(b),ordm(b)|ordm(a),所以ordm(a)=ordm(b)5.1 5.1 阶与原根阶与原根定理5.1.1 阶的基本性质若a n a l(mod m),(a,m)=

4、1,则nl(mod ordm(a)分析:不妨设nl,所以a l-n 1(mod m),所以ordm(a)|l-n 记n=ordm(a),则a0,a1,a n 1对模m两两不同余。分析:用反证法。若有0 i j n 1,使得 a i a j(mod m),则由(a,m)=1得到 a j i 1(mod m),这与j-in=ordm(a),与阶的定义矛盾,所以定理成立 特别的:g是原根g0,g1,g m 1是模m的缩系思路:g1,g2,g (m)这(m)个数两两不同余,所以一定组成缩系;另一方面,g1,g2,g (m)是缩系,所以当1l(m)时,gl g (m),从而ordm(g)=(m)5.1

5、5.1 阶与原根阶与原根定理5.1.1 阶的基本性质 a-1a 1(mod m),则ordm(a)=ordm(a-1)分析:(a-1a)n 1(mod m)则 (a-1)n 1(mod m)a n 1(mod m)记n=ordm(a),i0,ordm(a i)=s,则 分析:(a i)s 1(mod m)n=ordm(a)|is 则最小的s=所以,当(i,n)=1时,幂后阶不变,此时i的个数为(n)所以,有(n)个a i的阶为n=ordm(a)所以,如果有原根,则原根个数为 (m),(nins sniinin),(|),(snin|),(),(nin 5.1 5.1 阶与原根阶与原根定理5.1

6、.1 阶的基本性质若nm,则ordn(a)|ordm(a)分析:a ordm(a)1(mod m)=a ordm(a)1(mod n)若(m,n)=1,(a,mn)=1,则ordmn(a)=ordm(a),ordn(a)分析:设s=ordm(a),ordn(a),t=ordmn(a),由 ordn(a)|t,ordm(a)|t=s|t;a s 1(mod m),a s 1(mod n)=a s 1(mod mn)=t|s 推论:(m,n)=1,(a1,m)=(a2,n)=1,存在(a,mn)=1 使ordmn(a)=ordm(a1),ordn(a2)(ab,m)=1,(ordm(a),ordm

7、(b)=1则ordm(ab)=ordm(a)ordm(b)分析:设a ordm(b)ordm(ab)a ordm(b)ordm(ab)b ordm(b)ordm(ab)(a b)ordm(b)ordm(ab)1(mod m)=ordm(a)|ordm(b)ordm(ab),同理,ordm(b)|ordm(a)ordm(ab)所以,ordm(a)ordm(b)|ordm(ab)另一方面(a b)ordm(b)ordm(a)1(mod m),所以ordm(ab)|ordm(a)ordm(b)5.2 5.2 原根的存在条件原根的存在条件对于什么样的正整数m,模m的原根是存在?下面的定理不用证明,只需

8、应用定理5.2.1 若p奇素,则原根存在定理5.2.2 若p奇素,g是模p的一个原根,则g或g+p是模p2的原根,若g是模p2的原根,则g是模p的原根,定理5.2.3 模m有原根的必要条件是m=2,4,p或2p,其中p是奇素数,1 5.3 5.3 模素数原根的计算技巧模素数原根的计算技巧定理5.3.1n设奇素数p,p-1=,pi素,若对(a,p)=1满足 i=1,2,s 则a为p的原根思路:设ordp(a)=n,则n|p-1,若n1的整,g是其一个原根,(a,m)=1,则存在唯一整数r使 gr a(mod m)则r叫做以g为底的a对模m的一个指标,记为r=indga注:性质类似指数、对数,所以

9、有的人将这个称为指数5.4 5.4 指标指标7的指数表填表规则 a那行作乘法,ind a 那行作加法 ind a为1时,对应的a为起始的那个原根a123456ind7a0214535.5 5.5 应用应用EIGamal公钥密码体制n(1)选取大素数p和p的一个原根a,(a,p)=1,1apn(2)随机选取整数d,1dp-1,计算b ad(mod p);p,a,b为公钥,d为私钥n(3)加密:对0mp,秘密的随机选取整数k,1kp-1,加密后密文为c=(c1,c2),c1 ak(mod p),c2 mbk(mod p)n(4)解密:明文m c2(c1 d)-1(mod p)分析:c2(c1)d

10、mbk(ak d)-1 m adk(ak d)-1 m(mod p)4.2 4.2 勒让德符号(勒让德符号(Legendre)高斯(gauss)引理 现要证这(p-1)/2个数各不相同,只需证ri=p-sj,若ri=p-sj,则ri+sj0(mod p).又因为rita(mod p),sjua(mod p),其中t和u是小于或等于(p-1)/2的两个正整数.于是,(t+u)a(mod p).因为,(a,p)=1,所以(t+u)0(mod p),这是不可能的,因为2t+up-1,故有:而此式左端故!21)(11psprmjjkii)(mod!21112/)1(11ppasrpmmjjkiimmp

11、a14.2 4.2 勒让德符号(勒让德符号(Legendre)定理定理4.2.1 4.2.1 若p是奇素数,则 思路:在高斯引理中,令a=2,则:2,22,23,3,(p-1)/22已在1与p之间,令计算满足p/22kp,有p/4kp/2的k个数则:令 p=8a+r,r=1,3,5,7,则得:该定理表明,若 p1(mod 8),则 2是模p的二次剩余;若 p=3(mod p),则2是模p的二次非剩余.8/)1(212pp,42ppm)2(mod0,1,1,0422rram4.2 4.2 勒让德符号(勒让德符号(Legendre)定理定理4.2.14.2.1 思路2:当1k(p-1)/2时,有:

12、令:则:由高斯引理的证明知ri和p-sj与1,2,(p-1)/2中之一相同(1ik,1jm),因此得:(1)又 (2),11,ptpkaqtpqkakkkk,11mjjkiisSrRSRtpkk2/)1(1SmpRpp)1(2121812SRqptqpkaappkkpkkpkkpk2/)1(12/)1(12/)1(12/)1(12814.2 4.2 勒让德符号(勒让德符号(Legendre)定理定理4.2.14.2.1(3)-(2)故若a=2 若a奇数 Smpqpappkk2)1(812/)1(12)2(mod2/)1(1pkkqm)2(mod812pm4.3 4.3 二次互反定理二次互反定理

13、定理4.3.1 二次互反定理:数论酵母若p和q是二奇素数,且pq,则有:思路:同理剩下只需证明:(3)2/)1(2/)1(1qppqqp2/)1(12/)1(1111pkpkkpkqqmpq2/)1(11pkpkpqp2)1(2)1(2/)1(12/)1(1qpqkppkqpkpk4.3 4.3 二次互反定理二次互反定理定理4.3.1 作为(0,0),(0,q/2),(p/2,0),(p/2,q/2)为顶点的长方型连接(0,0)和(p/2,q/2)之对角线l,则l上无整点(即二座标为整数的点).否则有整点(x,y)在l上,则xq-yp=0,其中,1x(p-1)/2,1y(p-1)/2,即得p|

14、x,q|y,这是不可能的.由于长方型内的整点数为(p-1)/2.(q-1)/2,而l下三角型之整点数为:l上三角形中之整点数为:因此,(3)得证明.2,0q2,2qp0,2p0,0,2/)1(1pkpkq,2/)1(1pkqkp4.3 4.3 二次互反定理二次互反定理推论 若pq3(mod 4),则:否则,这是因为,除非pq3(mod 4),否则(p-1)(q-1)/4总是偶数,pqqp.pqqp4.3 4.3 二次互反定理二次互反定理对于x2a(mod p),(p,a)=1设设 ,则有则有:当p3(mod 4)时,解为a(p+1)/4.当p5(mod 8)时,a(p-1)/41(mod p)

15、时,a(p+3)/8为(1)的解;当a(p-1)/4-1(mod p)时,a(p+3)/8为(1)的解.思路:当p3(mod 4)时,a(p-1)/21(mod p),即(a(p+1)/4)2 a(mod p).当p5(mod 8)时,先求a=-1的解,由威尔逊定理知:因a(p-1)/21(mod p).a满足:a(p-1)/41(mod p)或a(p-1)/4-1(mod p)时,分别给出(a(p+3)/8)2a(mod p)和:1pa!21p.mod!21122121321!112pppppppp.mod)!21(28/)3(paapp4.3 4.3 二次互反定理二次互反定理对于x2a(m

16、od p),(p,a)=1设设 ,则有则有:p1(mod 8),则同余式(1)有解a(s+1)/2btk,其中s满足:p=2kS+1,2|s,tk0是某个整数.思路:由p1(mod 8),可设p=2kS+1,k3,2|s,所以 所以,1(mod p)故有非负整数 t2=sf(f=0或1)使下式成立:故又有非负整数 t3=sf(f=0或1)使下式成立:因为k是有限整数,故必有一非负整数tk使得:asb2tk1(mod p)于是得:as+1b2tka(mod p)即:(a(s+1)/2 btk)2a(mod p)1pa,1,1pbpa)(mod1),(mod11122pbpasskkska22)(

17、mod121222pbatskk)(mod132322pbatskk4.4 4.4 雅可比符号雅可比符号(Jacobi)中的素数p扩展为合数m 定理4.4.1 设m是一正奇数,pi是素数,(m,a)=1,则:有 称为(Jacobi)符号.性质:设m,n是正奇数.若ab(mod m)和(a,m)=1,则若(a,m)=1和(a,n)=1,则若(a,m)=1和(b,m)=1,则pa,1siipmsiipama1;mbma;mnanama.mabmbma4.4 4.4 雅可比符号雅可比符号(Jacobi)性质:m奇数 思路:则 即故:pi1(mod 8),1is,故则.112/)1(mm.128/)1

18、(2mm.11m,1111111111sjiiisiisiisiipppppmsiipm14mod11siipm12mod2/121 2/)1(2/)1(111111mpsiisiipmsjijisiisiippppm12212122,11111164mod11122siipm2mod8/18/1122siipm4.4 4.4 雅可比符号雅可比符号(Jacobi)定理4.4.2 若m与n是二正奇数,且(m,n)=1,则:思路:令 均为素数,则:而 故:因此:21211nmmnnmjitjjsiiqpqnpm,11kijsitjjipqqpmnnm111tjjsiisitjjiqpqpk1111

19、1211211211212mod1211211mpsii2mod121121nmk21211nmmnnm对于一个明文消息m(0=m n),如果将其加密成m 自身的话,则称m 为RSA 的不动点,也称m为未隐匿的消息。不管加密解密参数如何选取,RSA系统中至少存在九个不动点,即对任意选择的密钥,至少有9个明文消息不会以加密来隐匿,其中有三个是一1,0和1,其余6个明文不动点与参数选取有关,强素数P应当满足以下4个条件:(1)p是一个位数足够长的随机选取的素数;(2)p一1含有一个大的素因子R;(3)p+1含有一个大的素因子S;(4)R-1含有一个大的素因子t4.4 4.4 雅可比符号雅可比符号(Jacobi),1ma1ma,192

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|