《(精品)第四章 原根与指数.ppt》由会员分享，可在线阅读，更多相关《(精品)第四章 原根与指数.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、巫玲巫玲WW第四章第四章 原根与指数原根与指数PRIMITIVE ROOT4.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 n设 ,m 1,(a,m)=1，则使 a d 1(mod m)(1)成立的最小的正整数d，称为a对模m的指数，为ordm(a)，在不致误会的情况下，简记为ord(a)。指数也称为阶4.1 指数与原根指数与原根例如：ordm(1)=1,or
2、d2(-1)=1,ordm(-1)=2(m2),ord17(3)=16注意：n如果（a,m）1，则规定ordm(a)=0n以后，在谈到a对模m的指数时，总假定m1，(a,m)=1 n有的使用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的因数a123456ord7(a)1363624.1 指数与原根指数与原根模10的指数表 11 1(mod 10)
3、34 1(mod 10)74 1(mod 10)92 1(mod 10)观察：3与7的指数同,是9的指数的2倍 所有的指数都是4的因数,4是什么？a1379ord10(a)14424.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的原根原根也可能没有，如模
4、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
5、、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)分
6、析：(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 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,g
7、2,g (m)这(m)个数两两不同余，所以一定组成缩系;另一方面,g1,g2,g (m)是缩系，所以当1l (m)时，glg (m)，从而ordm(g)=(m)4.1 指数与原根指数与原根观察n这是一个循环(循环多长?)n如果用2来做这个循环，就会出现2-4-1-2n如果用5来做，5-4-6-2-3-1-5n观察指数:对于2 2-4-6 对于5 5-(10)4-(15)3-(20)2-(25)1-aa2a3a4a5a6632645124.1 指数与原根指数与原根性质4-1 指数的基本性质 若a n a l(mod m)，(a,m)=1，则nl(mod ordm(a)分析：不妨设nl，所以a l
8、-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
9、)/(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)a123456ord7(a)136362练习练习观察模7的所有缩系元素的指数7的原根(7)=(6)=2个，6有因素1、2、3、6所以存在：3指数的(3)=2个2指数的(2)=1个1指数的(1)=1个a123456ord7(a)136362练习练习模7的原根的个数为(7)=(6)=2由前例 3是模7的原根,6的缩系元素有1，5所以35(mod 7)3*22 12 5所以
10、模7的两个原根：3和5作业(2)：85页5题，要求求出所有原根，写出缩系每个元素的指数求出模7的所有原根练习练习计算7的缩系中每个元素的指数方法1：依次计算幂（如前）方法2：n首先找到一个原根，3(从2开始计算指数找原根)n用此原根生成缩系：322,336,344,355,361(mod 7)n则：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)=64.1 指数与原根指数与原根性质4-1 指数的基本性质若nm，则ordn(a)|ordm(a)分
11、析：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)，所以
12、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(
13、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)=
14、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有原根的必要条
15、件是m=2，4，p或2p，其中p是奇素数，1 4.3 模素数原根的计算技巧模素数原根的计算技巧定理4-3n设奇素数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注：n类似于对数，所以这个解方程问题叫做离散对数问题4.4 指数指数7的指数表填表规则 a那行作乘法，ind a 那行作加法 ind a为1时，对应的a为起始的那个原根a123456ind3a021453aa2a3a4a5a6
16、63264512练习练习类似于解对数方程：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)a123456ind3a021453练习练习法一：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(mo
17、d 6)x2(mod 6)仍然是6指数模指数，底数模m解方程 6*3x 5(mod 7)a123456ind3a0214534.5 应用应用三大难题之一：离散对数问题ngr a(mod m)，已知g,a,m，求r困难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(c
18、1)-d mbk(ak d)-1 m adk(ak d)-1 m(mod p)应用应用密钥交换n对称加密需要Diffie-Hellman密钥交换n素数p与其原根a为公开整数n设A,B希望交换密钥，则A选择随机数XAp，计算YA aXA(mod p)；类似的B选择随机数XBp，计算YB aXB(mod p)，X私有，Y公开nA计算KA(YB)XA(mod p)将其作为自身密钥nB计算KB(YA)XB(mod p)将其作为自身密钥nKA=KB实现了密钥的交换应用应用RSA定点攻击n第三者截获密文C后，反复计算e次幂 ce me2 ce2 me3（mod n）一旦 cet c me（mod n）=m
19、 ce(t-1)（mod n）nt不是很大时这种攻击可行n如何避免？如何让t很大？n若m模n的指数为k，t可取的最小值为e模k的指数n这个指数为(k)的因子，所以(k)应有大素因子n而k是(n)=(p-1)(q-1)的因子n所以p-1,q-1应有大素因子强素数 总结总结原根n缩系中指数与欧拉函数相等的数n模m有原根的必要条件是m=2，4，p或2p，其中p是奇素数，1指数：nak 1(mod m)成立的最小正整数k,写作ordm(a)或m(a)n若指数与欧拉函数不等，指数也整除欧拉函数n等指数：同余、互逆数的指数相同如何计算指数？n幂从小到大取欧拉函数的因数试算，直到1如何计算原根n计算出的指数
20、等于欧拉函数练习练习计算ord11(3)n首先计算(11)=10，所以指数可能为1,2,5,10n从小到大依次试算n313,329,351(mod 11)，所以ord11(3)=5n根据这个结论可以推出 ord11(14)=5=ord11(4)n可以推出ord11(-3)=ord11(-1)*ord11(3)=10n所以-38是原根，原根一共(10)=4个n所以823，8329 726，87221212，89227277，即2、6、7、8是原根总结总结寻找一个原根的技巧:nordm(a)|(m)n(m,n)=1，(a,mn)=1，则ordmn(a)=ordm(a),ordn(a)n(ab,m)
21、=1，(ordm(a),ordm(b)=1则ordm(ab)=ordm(a)ordm(b)n奇素数p，p-1=练习练习求模41的原根情况n(11)=40,现在只要考察x8,x20n从2开始,因为n2810,2201(mod 41);n381,320-1(mod 41);n4820,4201(mod 41);n5818,5201(mod 41);n6810,620-1(mod 41);n所以6是模41的原根练习练习求模41的原根情况n因为:6236,63-3011,6425,65-5527(mod 41);n6639,6729,6810,6919,61032,61128(mod 41);n612
22、4,61324,61421,6153,61618,61726(mod 41);n61833,61934,62040,62135,6225,62330(mod 41);n62416,62514,6262,62712,62831,62922(mod 41);n6309,63113,63237,63317,63420,63538(mod 41);n63623,63715,6388,6397,6401(mod 41);练习练习求模41的原根情况n所以:指数为1的元素有(1)=1个,是1;n指数为2的元素有(2)=1个,是62040(mod 41);n指数为4的元素有(4)=2个,是61032,6309
23、(mod 41);n指数为5的元素有(5)=4个,是10，18，16，37n指数为8的元素有(8)=4个,是27，3，14，38n指数为10的元素有(10)=4个,是25，4，31，23n指数为20的元素有(20)=8个,是36，39，21，33，5，2，20，8n指数为40的元素有(40)=16个,是6，11，29，19，28，24，26，34，35，30，12，22，13，17，15，7总结总结指数的价值：n幂化简原根的价值n生成元：生成缩系所有元素n,gdnd遍历(p)的缩系(p)个)，gd遍历模p的原根ng是原根的时候幂与(计算幂后的)值形成置换aa2a3a4a5a6326451总结总
24、结原根的价值之二n可以推出其余所有缩系元素的指数nordm(ai)=ordm(a)/(ordm(a),i)n可以根据幂对缩系元素按指数分类a7a8a9a107361aa2a3a4a5a62485109练习练习计算同余方程xk 1(mod 11)的解的个数n首先计算(11)=10，所以指数可能为1,2,5,10nk=1时，有(1)=1个；nk=2时，有(2)=1个nk=5时，有(5)=4个；nk=10时，有(10)=4个n考虑不周，k=3,4等其他数时呢x 1(mod 11)是k等于任何值的解练习练习计算同余方程xk 1(mod 11)的解的个数关键在于指数可能可以化简指数可取1,2,5,10,
25、指数为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)