第五章 原根与指标.ppt

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) ，在不致误会的情况下

2、，简记为ord(a)。 例如：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的指数表,模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 ord(a)q+r a r 1 (

3、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(a) 分析：不妨设nl ，所

4、以a l-n 1 (mod m)，所以ordm(a)| l-n 记n= ordm(a) ，则a0, a1, , a n 1对模m两两不同余。 分析：用反证法。若有0 i 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.1.1 阶的基本性质 a-1a 1(mod m)，则ordm(a)= ordm(a-1) 分析： (a-1a ) n 1(mod m)则 (a-1) n

5、 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 阶的基本性质 若nm ，则ordn(a)| ordm(a) 分析： a ordm (a) 1 (mod m) = a ordm (a) 1 (mod n) 若(m, n) = 1，(a, mn) = 1，则ord

6、mn(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(b)=1则ordm(ab)=ordm(a)ordm(b) 分析：设a ordm (b) ordm (ab)

7、 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 原根的存在条件,对于什么样的正整数m，模m的原根是存在? 下面的定理不用证明，只需应用 定理5.2.1 若p奇素，则原根存在 定理5.2.2 若

8、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，若np-1则存在某个素数pi|(p-1)/n 即： (p-1)/n= pi u即 与条件矛盾，所以n=p-1,5.4 指标,定义5.4.1 设m1的整，g是其一个原根，(a,m)=1，则存在唯一整数r使 gr a (mod m) 则r叫做以g

9、为底的a对模m的一个指标，记为r=indga 注：性质类似指数、对数，所以有的人将这个称为指数,5.4 指标,7的指数表 填表规则 a那行作乘法 ，ind a 那行作加法 ind a为1时，对应的a为起始的那个原根,5.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), c2 mbk (mod p) (4)解密：明文m c2 ( c1

10、 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), 这是不可能的, 因为2t+up-1, 故有: 而此式左端 故,4.2 勒让德符

11、号（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中之一相同(1ik, 1jm), 因此得:

12、（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(

14、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)和:,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, 所以

15、 所以， 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),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 = m n) ,