第五章-原根与指标-优质课件_第1页
第五章-原根与指标-优质课件_第2页
第五章-原根与指标-优质课件_第3页
第五章-原根与指标-优质课件_第4页
第五章-原根与指标-优质课件_第5页
已阅读5页,还剩41页未读 继续免费阅读

下载本文档

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

文档简介

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

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

3、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.1 阶的基本性质若a n a l (mod m),(a, m) = 1,则nl (mod ordm(

4、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

5、(m) ,从而ordm(g) = (m)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)5.1 阶与原根定理5.1.1

6、阶的基本性质若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 使or

7、dmn(a)= ordm(a1),ordn(a2) (ab, m) =1, (ordm(a),ordm(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)

8、,所以ordm(ab)|ordm(a)ordm(b)5.2 原根的存在条件对于什么样的正整数m,模m的原根是存在?下面的定理不用证明,只需应用定理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.1设奇素数p,p-1= ,pi素,若对(a,p)=1满足 i=1,2,s 则a为p的原根思路:设ordp(a)=n,则n|p-1,若n1的整,g是其一个原根,(a,m)=1,则存在唯一

9、整数r使 gr a (mod m) 则r叫做以g为底的a对模m的一个指标,记为r=indga注:性质类似指数、对数,所以有的人将这个称为指数5.4 指标7的指数表填表规则 a那行作乘法 ,ind a 那行作加法 ind a为1时,对应的a为起始的那个原根a123456ind7a0214535.5 应用EIGamal公钥密码体制(1)选取大素数p和p的一个原根a,(a,p)=1,1ap(2)随机选取整数d,1dp-1,计算b ad (mod p);p,a,b为公钥,d为私钥(3)加密:对0mp,秘密的随机选取整数k,1kp-1,加密后密文为c=(c1 , c2 ), c1 ak (mod p),

10、 c2 mbk (mod p)(4)解密:明文m c2 ( c1 d) -1 (mod p)分析: c2 ( c1 ) d mbk (ak d) -1 m adk (ak d) -1 m (mod p)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), 这是不可能的, 因为

11、2t+up-1, 故有: 而此式左端故4.2 勒让德符号(Legendre)定理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的二次非剩余.4.2 勒让德符号(Legendre)定理4.2.1 思路2:当1k(p-1)/2时, 有:令: 则: 由高斯引理的证明知ri和p-sj与1, 2, , (p-1)/2中之一

12、相同(1ik, 1jm), 因此得:(1)又 (2)4.2 勒让德符号(Legendre)定理4.2.1(3)-(2)故若a=2 若a奇数 4.3 二次互反定理定理4.3.1 二次互反定理:数论酵母若p和q是二奇素数, 且pq, 则有:思路: 同理剩下只需证明:(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|x, q|y, 这是不可能的.

13、 由于长方型内的整点数为(p-1)/2.(q-1)/2, 而l下三角型之整点数为: l上三角形中之整点数为: 因此,(3)得证明.4.3 二次互反定理推论 若pq3(mod 4), 则: 否则, 这是因为, 除非pq3(mod 4),否则 (p-1)(q-1)/4总是偶数4.3 二次互反定理对于x2a(mod p), (p,a)=1设 ,则有:当p3(mod 4)时, 解为a(p+1)/4.当p5(mod 8)时, a(p-1)/41(mod p)时, a(p+3)/8为(1)的解; 当a(p-1)/4-1(mod p)时, a(p+3)/8为(1)的解.思路:当p3(mod 4)时, a(p

14、-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)和:4.3 二次互反定理对于x2a(mod 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(

15、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)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,则4.4 雅可比符号(Jacobi)性质:m奇数 思路 :则 即故:pi1(mod 8), 1is, 故则4.4 雅可比符号(Jacobi)定理4.4.2 若m与n是二正奇数, 且(m,n)=1, 则:思路:令 均为素数, 则: 而 故: 因此:对于一个明文消息m (0 =

温馨提示

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

评论

0/150

提交评论