第四章 原根与指数.ppt

1、巫玲 W,第四章 原根与指数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,

2、 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(mo

3、d 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没有原根,练习

4、,证明：5是模3与模6的原根，也是模32，2* 32的原根 (3)=2， (6)=(3)(2)=2 (32)=9-3=6, (2*32)=(2)(32)=6 5-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

5、,所以只需计算1、2、4、8、16 55(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

6、(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)=16 7*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)个数两两不同余，所以 一定组成缩

7、系;另一方面,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

8、23456(mod 3) 2 223456(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 )

9、=3 ord7(4)= ord7(2)/(ord7(2),2) =3/(2,3)=3 ord7(8)= ord7 (2)/(ord7(2),3) =3/(3,3)=1 ord7(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题，要求求出所有原根，写出

10、缩系每个元素的指数,求出模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

11、 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) 现在只

12、需直接计算361(mod 28)，所以ord28(3)= 6 上面利用的是 ，利用直接 因为(4，7)=1，所以ord28(3)=6,2=6,计算3模28的指数,练习,ord49(3)=？ (49)= 49-7=42 ord7(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)

13、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(

14、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的原根是存在? 下面的定理不用证明，只需应用 定理

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

16、7)，失败 取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? ind

17、3x 5(mod 6) 查表 x5(mod 7) 注意：模又恢复为7 当然也可以利用 ind5x 5ind5x 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

18、 应用,三大难题之一：离散对数问题 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),应

19、用,密钥交换 对称加密需要 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不是很大时这种攻击可行 如何避免？如

20、何让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

21、)=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)

22、,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); 6

23、124, 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的

24、元素有(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,总结,指数的价值： 幂化简 原根的价值 生成元：生成缩系所有元素 ,gd d遍历(p)的缩系(p)个)，gd遍历模p的原根 g是原根的时候幂与(计算幂后的)值形成置换,总结,原根的价值之二 可以推出其余所有缩系元素的指数 ordm(ai)=ordm(a)/(ordm(a),i) 可以根据幂对缩系元素按指数分类,练习,计算同余