第四章 原根与指数

巫玲巫玲Wuling751@Wuling751@第四章第四章 原根与指数原根与指数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 n设 ,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(m>2), ord17(3)=16¢注意：n如果（a,m）>1，则规定ordm(a)=0n以后，在谈到a对模m的指数时，总假定m>1，(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)136362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是什么？a1379ord10(a)14424.1 指数与原根指数与原根¢定理4-1 指数的基本性质① a n  1 (mod m)的充要条件是ordm(a)|n 分析：设n= ordm(a)q+r,0≤r< ordm(a),q,r∈Z则： 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) 521(mod 3) 是原根5-1(mod 6) 521(mod 6) 是原根55(mod 9) 52-2(mod 9) 53-1(mod 9)544(mod 9) 552(mod 9) 561(mod 9) 是原根55(mod 18) 527(mod 18) 53-1(mod 18)54-5(mod 18) 55-7(mod 18) 561(mod 18)是原根练习练习ord17(5)=？φ(17)=16,所以只需计算1、2、4、8、1655(mod 17) 528(mod 17) 5413(mod 17) 5816-1(mod 17) 5161(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 < j  n 1，使a i  a j (mod m)，则由(a, m) = 1得到 a j  i  1 (mod m)，这与j-ig0, g1, , g ψ(m) 1是模m的缩系思路：g1,g2,,g (m) 这 (m)个数两两不同余，所以一定组成缩系;另一方面,g1,g2,,g (m)是缩系，所以当1≤l≤ (m)时，gl≡g (m) ，从而ordm(g)= (m)4.1 指数与原根指数与原根¢观察n这是一个循环(循环多长?)n如果用2来做这个循环，就会出现2->4->1->2n如果用5来做，5->4->6->2->3->1->5……n观察指数:对于2 2->4->6 对于5 5->(10)4->(15)3->(20)2->(25)1->…aa2a3a4a5a6632645124.1 指数与原根指数与原根¢性质4-1 指数的基本性质④ 若a n  a l (mod m)，(a, m) = 1，则nl (mod ordm(a)) 分析：不妨设n≤l ，所以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) ，i>0, 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 )=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)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所以模7的两个原根：3和5作业(2)：85页5题，要求求出所有原根，写出缩系每个元素的指数¢求出模7的所有原根练习练习¢计算7的缩系中每个元素的指数¢方法1：依次计算幂（如前）¢方法2：n首先找到一个原根，3(从2开始计算指数找原根)n用此原根生成缩系：322, 336, 344, 355, 361 (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)=64.1 指数与原根指数与原根¢性质4-1 指数的基本性质⑧若nm ，则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)现在只需直接计算361(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)因为3681*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直接计算:224, 2111(mod 23)，所以ord23(2)=11用以前的方法再计算3的幂，如不行再计算5的……此时考虑只需找到一个ord23(a)=2，则ord23(2a)=22而ord23(-1)=2所以ord23(-2)=22，-2是原根，所以原根有φ(22)=10个(-2)315,(-2)514,(-2)710,(-2)917,(-2)1319(mod 23)(-2)157,(-2)175,(-2)1920,(-2)2111 (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-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为起始的那个原根a123456ind3a021453aa2a3a4a5a663264512练习练习类似于解对数方程：5ind3x ind33 1(mod 6) 为什么是6?ind3x 5(mod 6)查表 x5(mod 7) 注意：模又恢复为7当然也可以利用 ind5x5ind5x ind53 5(mod 6) ind5x 1(mod 6)直接 x5(mod 7) 作业（4）85页第8题¢解方程 x5  3 (mod 7)a123456ind3a021453练习练习法一： 6-1  -1 (mod 7)，所以原方程化简为3x  -5  2(mod 7)，所以xind33 ind32(mod 6) x2(mod 6) 仍然是6法二：ind36+xind33 ind35(mod 6) 3+x5(mod 6)x2(mod 6) 仍然是6指数模指数，底数模m¢解方程 6*3x  5 (mod 7)a123456ind3a0214534.5 应用应用¢三大难题之一：离散对数问题ngr  a (mod m)，已知g,a,m，求r困难¢EIGamal公钥密码体制n(1)选取大素数p和p的一个原根a，(a,p)=1,1,{gd}nd遍历φ(p)的缩系(φ(φ(p))个)，gd遍历模p的原根ng是原根的时候幂与(计算幂后的)值形成置换aa2a3a4a5a6326451总结总结¢原根的价值之二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,¢指数为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)各有哪些解？¢先找出每个指数对应的解，要计算指数先找出原根¢原根都是试找的，先看2¢224, 25-1, 2101(mod 11),所以2是模11的原根¢所以生成缩系中的其它元素¢224, 238, 245, 2510, 269 (mod 11)¢277, 283, 296, 2101 (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时有解x1(mod 11)¢k=2、4、6、8时有解x1(mod 11)和x10(mod 11)¢k=5时有解x1,3,4,5,9(mod 11)¢K=10时有解x1,2,3,4,5,6,7,8,9,10(mod 11)。