《原根与指数》PPT课件

巫玲Wuling751,第四章原根与指数PRIMITIVEROOT,4.0问题的引入,本章围绕的是解高指数方程xka(modm)主要利用的是欧拉定理a(m)1(modm)欧拉的不足：261(mod7)同时231(mod7),4.1指数与原根,对xk1(modm)，(x,m)=1时,肯定有解，但最小解？定义4-1设,m1,(a,m)=1，则使ad1(modm)(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的指数表111(mod7)231(mod7)361(mod7)431(mod7)561(mod7)621(mod7)观察：2与4的指数同，3与5的指数同所有的指数都是6的因数,4.1指数与原根,模10的指数表111(mod10)341(mod10)741(mod10)921(mod10)观察：3与7的指数同,是9的指数的2倍所有的指数都是4的因数,4是什么？,4.1指数与原根,定理4-1指数的基本性质an1(modm)的充要条件是ordm(a)|n分析：设n=ordm(a)q+r,0r4-1-2如果用5来做，5-4-6-2-3-1-5观察指数:对于22-4-6对于55-(10)4-(15)3-(20)2-(25)1-,4.1指数与原根,性质4-1指数的基本性质若anal(modm)，(a,m)=1，则nl(modordm(a)分析：不妨设nl，所以al-n1(modm)所以ordm(a)|l-n,练习,ord7(2)=323456(mod3)2223456(mod7)224,计算223456(mod7),4.1指数与原根,性质4-1指数的基本性质记n=ordm(a)，i0,ordm(ai)=s，则分析：(ai)s1(modm)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(mod7)3*22125所以模7的两个原根：3和5作业(2)：85页5题，要求求出所有原根，写出缩系每个元素的指数,求出模7的所有原根,练习,计算7的缩系中每个元素的指数方法1：依次计算幂（如前）方法2：首先找到一个原根，3(从2开始计算指数找原根)用此原根生成缩系：322,336,344,355,361(mod7)则：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)分析：aordm(a)1(modm)=aordm(a)1(modn)对于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;as1(modm),as1(modn)=as1(modmn)=t|s,练习,ord28(3)=？(28)=(4)(7)=2*6=12本来需要计算幂为2、3、4、6但是因为ord7(3)=6，ord4(3)=2所以6|ord28(3)现在只需直接计算361(mod28)，所以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(mod49)所以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)分析：设aordm(b)ordm(ab)aordm(b)ordm(ab)bordm(b)ordm(ab)(ab)ordm(b)ordm(ab)1(modm)=ordm(a)|ordm(b)ordm(ab),同理，ordm(b)|ordm(a)ordm(ab)所以，ordm(a)ordm(b)|ordm(ab)另一方面(ab)ordm(b)ordm(a)1(modm),所以ordm(ab)|ordm(a)ordm(b)价值：简化求原根,练习,(23)=22，指数可能为1、2、11、22直接计算:224,2111(mod23)，所以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(mod23)(-2)157,(-2)175,(-2)1920,(-2)2111(mod23)所以模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，若n1的整，g是其一个原根，(a,m)=1，则存在唯一整数r使gra(modm)则r叫做以g为底的a对模m的一个指标，记为r=indga注：类似于对数，所以这个解方程问题叫做离散对数问题,4.4指数,7的指数表填表规则a那行作乘法，inda那行作加法inda为1时，对应的a为起始的那个原根,练习,类似于解对数方程：5ind3xind331(mod6)为什么是6?ind3x5(mod6)查表x5(mod7)注意：模又恢复为7当然也可以利用ind5x5ind5xind535(mod6)ind5x1(mod6)直接x5(mod7)作业（4）85页第8题,解方程x53(mod7),练习,法一：6-1-1(mod7)，所以原方程化简为3x-52(mod7)，所以xind33ind32(mod6)x2(mod6)仍然是6法二：ind36+xind33ind35(mod6)3+x5(mod6)x2(mod6)仍然是6指数模指数，底数模m,解方程6*3x5(mod7),4.5应用,三大难题之一：离散对数问题gra(modm)，已知g,a,m，求r困难EIGamal公钥密码体制(1)选取大素数p和p的一个原根a，(a,p)=1,1ap(2)选取整数d，1dp-1，计算bad(modp)；p,a,b为公钥，d为私钥(3)加密：对0mp，秘密的随机选取整数k,1kp-1,加密后密文为c=(c1，c2),c1ak(modp),c2mbk(modp)(4)解密：明文mc2(c1d)-1(modp)分析：c2(c1)-dmbk(akd)-1madk(akd)-1m(modp),应用,密钥交换对称加密需要Diffie-Hellman密钥交换素数p与其原根a为公开整数设A,B希望交换密钥，则A选择随机数XAp，计算YAaXA(modp)；类似的B选择随机数XBp，计算YBaXB(modp)，X私有，Y公开A计算KA(YB)XA(modp)将其作为自身密钥B计算KB(YA)XB(modp)将其作为自身密钥KA=KB实现了密钥的交换,应用,RSA定点攻击第三者截获密文C后，反复计算e次幂ceme2ce2me3（modn）一旦cetcme（modn）=mce(t-1)（modn）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指数：ak1(modm)成立的最小正整数k,写作ordm(a)或m(a)若指数与欧拉函数不等，指数也整除欧拉函数等指数：同余、互逆数的指数相同如何计算指数？幂从小到大取欧拉函数的因数试算，直到1如何计算原根计算出的指数等于欧拉函数,练习,计算ord11(3)首先计算(11)=10，所以指数可能为1,2,5,10从小到大依次试算313,329,351(mod11)，所以ord11(3)=5根据这个结论可以推出ord11(14)=5=ord11(4)可以推出ord11(-3)=ord11(-1)*ord11(3)=10所以-38是原根，原根一共(10)=4个所以823，8329726，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(mod41);381,320-1(mod41);4820,4201(mod41);5818,5201(mod41);6810,620-1(mod41);所以6是模41的原根,练习,求模41的原根情况因为:6236,63-3011,6425,65-5527(mod41);6639,6729,6810,6919,61032,61128(mod41);6124,61324,61421,6153,61618,61726(mod41);61833,61934,62040,62135,6225,62330(mod41);62416,62514,6262,62712,62831,62922(mod41);6309,63113,63237,63317,63420,63538(mod41);63623,63715,6388,6397,6401(mod41);,练习,求模41的原根情况所以:指数为1的元素有(1)=1个,是1;指数为2的元素有(2)=1个,是62040(mod41);指数为4的元素有(4)=2个,是61032,6309(mod41);指数为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)可以根据幂对缩系元素按指数分类,练习,计算同余方程xk1(mod11)的解的个数,首先计算(11)=10，所以指数可能为1,2,5,10k=1时，有(1)=1个；k=2时，有(2)=1个k=5时，有(5)=4个；k=10时，有(10)=4个考虑不周，k=3,4等其他数时呢x1(mod11)是k等于任何值的解,练习,计算同余方程xk1(