《原根与指数》PPT课件.ppt

巫玲,第四章 原根与指数PRIMITIVE ROOT,4.0 问题的引入,本章围绕的是解高指数方程 xk a(mod m)主要利用的是欧拉定理 a(m)1(mod m)欧拉的不足：26 1(mod 7)同时23 1(mod 7),4.1 指数与原根,对xk 1(mod m)，(x,m)=1时,肯定有解，但最小解？定义4-1 设,m 1,(a,m)=1，则使 a d 1(mod m)(1)成立的最小的正整数d，称为a对模m的指数，为ordm(a)，在不致误会的情况下，简记为ord(a)。指数也称为阶,4.1 指数与原根,例如：ordm(1)=1,ord2(-1)=1,ordm(-1)=2(m2),ord17(3)=16注意：如果（a,m）1，则规定ordm(a)=0以后，在谈到a对模m的指数时，总假定m1，(a,m)=1 有的使用ordm(a)等同的符号是 m(a)，(a)，但ordm(a)更常用,4.1 指数与原根,模7的指数表 11 1(mod 7)23 1(mod 7)36 1(mod 7)43 1(mod 7)56 1(mod 7)62 1(mod 7)观察：2与4的指数同，3与5的指数同 所有的指数都是6的因数,4.1 指数与原根,模10的指数表 11 1(mod 10)34 1(mod 10)74 1(mod 10)92 1(mod 10)观察：3与7的指数同,是9的指数的2倍 所有的指数都是4的因数,4是什么？,4.1 指数与原根,定理4-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(mod m)，因为ordm(a)最小，所以r=0 推论：ordm(a)|(m)若ordm(a)=(m)称a是模m的原根（也写作元根）如，3和5是模7的原根，3和7是模10的原根原根也可能没有，如模15、8没有原根,练习,证明：5是模3与模6的原根，也是模32，2*32的原根(3)=2，(6)=(3)(2)=2(32)=9-3=6,(2*32)=(2)(32)=65-1(mod 3)521(mod 3)是原根5-1(mod 6)521(mod 6)是原根55(mod 9)52-2(mod 9)53-1(mod 9)544(mod 9)552(mod 9)561(mod 9)是原根55(mod 18)527(mod 18)53-1(mod 18)54-5(mod 18)55-7(mod 18)561(mod 18)是原根,练习,ord17(5)=？(17)=16,所以只需计算1、2、4、8、1655(mod 17)528(mod 17)5413(mod 17)5816-1(mod 17)5161(mod 17)所以ord17(5)=16，5是模17的原根作业（1）：84页，1,例4-5 计算5模17的指数,4.1 指数与原根,性质4-1 指数的基本性质若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)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),练习,ord17(39)=ord17(5)=167*5=1(mod 17)ord17(7)=ord17(5)=16,计算39,7模17的指数,4.1 指数与原根,性质4-1 指数的基本性质记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)时，glg(m)，从而ordm(g)=(m),4.1 指数与原根,观察这是一个循环(循环多长?)如果用2来做这个循环，就会出现2-4-1-2如果用5来做，5-4-6-2-3-1-5观察指数:对于2 2-4-6 对于5 5-(10)4-(15)3-(20)2-(25)1-,4.1 指数与原根,性质4-1 指数的基本性质 若a n a l(mod m)，(a,m)=1，则nl(mod ordm(a)分析：不妨设nl，所以a l-n 1(mod m)所以ordm(a)|l-n,练习,ord7(2)=3 23456(mod 3)2223456(mod 7)22 4,计算223456(mod 7),4.1 指数与原根,性质4-1 指数的基本性质 记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 同指数,n=ordm(a)所以，如果有原根，则原根个数为(m)（30页完系的分解）,练习,观察模7的所有缩系元素的指数ord7(2)=ord7(9)=ord7(3)/(ord7(3),2)=3ord7(4)=ord7(2)/(ord7(2),2)=3/(2,3)=3ord7(8)=ord7(2)/(ord7(2),3)=3/(3,3)=1ord7(16)=3/(4,3)=3=ord7(2),练习,观察模7的所有缩系元素的指数7的原根(7)=(6)=2个，6有因素1、2、3、6所以存在：3指数的(3)=2个2指数的(2)=1个1指数的(1)=1个,练习,模7的原根的个数为(7)=(6)=2由前例 3是模7的原根,6的缩系元素有1，5所以35(mod 7)3*22 12 5所以模7的两个原根：3和5作业(2)：85页5题，要求求出所有原根，写出缩系每个元素的指数,求出模7的所有原根,练习,计算7的缩系中每个元素的指数方法1：依次计算幂（如前）方法2：首先找到一个原根，3(从2开始计算指数找原根)用此原根生成缩系：322,336,344,355,361(mod 7)则：ord7(2)=6/(2,6)=3;ord7(6)=6/(3,6)=2;ord7(4)=6/(4,6)=3;ord7(5)=6/(5,6)=6;ord7(1)=6/(6,6)=1;再加上ord7(3)=6,4.1 指数与原根,性质4-1 指数的基本性质若nm，则ordn(a)|ordm(a)分析：a ordm(a)1(mod m)=a ordm(a)1(mod n)对于m=pe的情况特别有用若(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,练习,ord28(3)=？(28)=(4)(7)=2*6=12本来需要计算幂为2、3、4、6但是因为ord7(3)=6，ord4(3)=2所以6|ord28(3)现在只需直接计算361(mod 28)，所以ord28(3)=6上面利用的是，利用直接因为(4，7)=1，所以ord28(3)=6,2=6,计算3模28的指数,练习,ord49(3)=？(49)=49-7=42ord7(3)=6，所以6|ord49(3)因为3681*9-17*9-2*3-6(mod 49)所以ord49(3)=42作业(3)：84页，2（1)(3）,计算3模49的指数,4.1 指数与原根,性质4-1 指数的基本性质(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),所以ordm(ab)|ordm(a)ordm(b)价值：简化求原根,练习,(23)=22，指数可能为1、2、11、22直接计算:224,2111(mod 23)，所以ord23(2)=11用以前的方法再计算3的幂，如不行再计算5的此时考虑只需找到一个ord23(a)=2，则ord23(2a)=22而ord23(-1)=2所以ord23(-2)=22，-2是原根，所以原根有(22)=10个(-2)315,(-2)514,(-2)710,(-2)917,(-2)1319(mod 23)(-2)157,(-2)175,(-2)1920,(-2)2111(mod 23)所以模23的原根有：5,7,10,11,14,15,17,19,20,21,计算模23的原根,4.2 原根的存在条件,对于什么样的正整数m，模m的原根是存在?下面的定理不用证明，只需应用定理 若p奇素，则原根存在定理 若p奇素，g是模p的一个原根，则g或g+p是模p2的原根，若g是模p2的原根，则g是模p的原根，定理4-2 模m有原根的必要条件是m=2，4，p或2p，其中p是奇素数，1,4.3 模素数原根的计算技巧,定理4-3设奇素数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,练习,求模47的一个原根首先分解47-1=2*23(a,47)=1,取a=2,223 1(mod 47)，失败取a=3,323 1(mod 47)，失败取a=5,523-1(mod 47)，52 25(mod 47)，所以5是模47的一个原根,4.4 指标,定义4-2 设m1的整，g是其一个原根，(a,m)=1，则存在唯一整数r使 gr a(mod m)则r叫做以g为底的a对模m的一个指标，记为r=indga注：类似于对数，所以这个解方程问题叫做离散对数问题,4.4 指数,7的指数表填表规则 a那行作乘法，ind a 那行作加法 ind a为1时，对应的a为起始的那个原根,练习,类似于解对数方程：5ind3x ind33 1(mod 6)为什么是6?ind3x 5(mod 6)查表 x5(mod 7)注意：模又恢复为7当然也可以利用 ind5x5ind5x ind53 5(mod 6)ind5x 1(mod 6)直接 x5(mod 7)作业（4）85页第8题,解方程 x5 3(mod 7),练习,法一：6-1-1(mod 7)，所以原方程化简为3x-5 2(mod 7)，所以xind33 ind32(mod 6)x2(mod 6)仍然是6法二：ind36+xind33 ind35(mod 6)3+x5(mod 6)x2(mod 6)仍然是6指数模指数，底数模m,解方程 6*3x 5(mod 7),4.5 应用,三大难题之一：离散对数问题gr a(mod m)，已知g,a,m，求r困难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 d)-1(mod p)分析：c2(c1)-d mbk(ak d)-1 m adk(ak d)-1 m(mod p),应用,密钥交换对称加密需要Diffie-Hellman密钥交换素数p与其原根a为公开整数设A,B希望交换密钥，则A选择随机数XAp，计算YA aXA(mod p)；类似的B选择随机数XBp，计算YB aXB(mod p)，X私有，Y公开A计算KA(YB)XA(mod p)将其作为自身密钥B计算KB(YA)XB(mod p)将其作为自身密钥KA=KB实现了密钥的交换,应用,RSA定点攻击第三者截获密文C后，反复计算e次幂 ce me2 ce2 me3（mod n）一旦 cet c me（mod n）=m ce(t-1)（mod n）t不是很大时这种攻击可行如何避免？如何让t很大？若m模n的指数为k，t可取的最小值为e模k的指数这个指数为(k)的因子，所以(k)应有大素因子而k是(n)=(p-1)(q-1)的因子所以p-1,q-1应有大素因子强素数,总结,原根缩系中指数与欧拉函数相等的数模m有原根的必要条件是m=2，4，p或2p，其中p是奇素数，1指数：ak 1(mod m)成立的最小正整数k,写作ordm(a)或m(a)若指数与欧拉函数不等，指数也整除欧拉函数等指数：同余、互逆数的指数相同如何计算指数？幂从小到大取欧拉函数的因数试算，直到1如何计算原根计算出的指数等于欧拉函数,练习,计算ord11(3)首先计算(11)=10，所以指数可能为1,2,5,10从小到大依次试算313,329,351(mod 11)，所以ord11(3)=5根据这个结论可以推出 ord11(14)=5=ord11(4)可以推出ord11(-3)=ord11(-1)*ord11(3)=10所以-38是原根，原根一共(10)=4个所以823，8329 726，87221212，89227277，即2、6、7、8是原根,总结,寻找一个原根的技巧:ordm(a)|(m)(m,n)=1，(a,mn)=1，则ordmn(a)=ordm(a),ordn(a)(ab,m)=1，(ordm(a),ordm(b)=1则ordm(ab)=ordm(a)ordm(b)奇素数p，p-1=,练习,求模41的原根情况(11)=40,现在只要考察x8,x20从2开始,因为2810,2201(mod 41);381,320-1(mod 41);4820,4201(mod 41);5818,5201(mod 41);6810,620-1(mod 41);所以6是模41的原根,练习,求模41的原根情况因为:6236,63-3011,6425,65-5527(mod 41);6639,6729,6810,6919,61032,61128(mod 41);6124,61324,61421,6153,61618,61726(mod 41);61833,61934,62040,62135,6225,62330(mod 41);62416,62514,6262,62712,62831,62922(mod 41);6309,63113,63237,63317,63420,63538(mod 41);63623,63715,6388,6397,6401(mod 41);,练习,求模41的原根情况所以:指数为1的元素有(1)=1个,是1;指数为2的元素有(2)=1个,是62040(mod 41);指数为4的元素有(4)=2个,是61032,6309(mod 41);指数为5的元素有(5)=4个,是10，18，16，37指数为8的元素有(8)=4个,是27，3，14，38指数为10的元素有(10)=4个,是25，4，31，23指数为20的元素有(20)=8个,是36，39，21，33，5，2，20，8指数为40的元素有(40)=16个,是6，11，29，19，28，24，26，34，35，30，12，22，13，17，15，7,总结,指数的价值：幂化简原根的价值生成元：生成缩系所有元素,gdd遍历(p)的缩系(p)个)，gd遍历模p的原根g是原根的时候幂与(计算幂后的)值形成置换,总结,原根的价值之二可以推出其余所有缩系元素的指数ordm(ai)=ordm(a)/(ordm(a),i)可以根据幂对缩系元素按指数分类,练习,计算同余方程xk 1(mod 11)的解的个数,首先计算(11)=10，所以指数可能为1,2,5,10k=1时，有(1)=1个；k=2时，有(2)=1个k=5时，有(5)=4个；k=10时，有(10)=4个考虑不周，k=3,4等其他数时呢x 1(mod 11)是k等于任何值的解,练习,计算同余方程xk 1(mod 11)的解的个数,关键在于指数可能可以化简指数可取1,2,5,10,指数为1时，有1个解，此时k可取1的倍数，即1-10任意数指数为2时，有1个解，此时k取2的倍数，即2,4,6,8,10指数为5时，有4个解，此时k取5的倍数，即5,10指数为10时，有4个解，此时k取10综合：k=1,3,7,9有1个解，k=2,4,6,8有两个解，k=5有5个解，k=10有10个解,练习,进一步：xk 1(mod 11)各有哪些解？,先找出每个指数对应的解，要计算指数先找出原根原根都是试找的，先看2224,25-1,2101(mod 11),所以2是模11的原根所以生成缩系中的其它元素224,238,245,2510,269(mod 11)277,283,296,2101(mod 11)所以原根有：2、8、7、6（幂与10互质）指数为5的有：4、5、9、3（幂与10最大公约2）指数为2的有：10指数为1的有1,练习,进一步：xk 1(mod 11)各有哪些解？,所以原根有：2、8、7、6（幂与10互质）指数为5的有：4、5、9、3（幂与10最大公约2）指数为2的有：10指数为1的有1所以k=1、3、7、9时有解x1(mod 11)k=2、4、6、8时有解x1(mod 11)和x10(mod 11)k=5时有解x1,3,4,5,9(mod 11)K=10时有解x1,2,3,4,5,6,7,8,9,10(mod 11),