原根及其应用

1、安庆师范学院数学与计算科学学院2009届毕业论文原根及其应用作者：XXX指导老师：XXX摘要本文介绍了指数与原根的定义以及它们的一些有关性质，并给岀了关于模m的原根存在的几个充分必要条件.从原根与同余方程解的关系角度揭示了当模m存在原根时所具有的一些本质特性最后讨论了基于离散对数问题的公钥密码体制即ElGamal密码体制，体现了原根在密码学方面的应用.关键词 指数原根剩余类ElGamal密码体制1引言在这篇文章中，我们从欧拉定理引出指数的定义，进而得出原根定义，以及指数与原根的一些有关性质，接着我们经验证前30个正整数的原根存在的情况推断出一般整数原根存在的条件，并给出证明还从原根与同余方程解

2、的关系这个角度出发，揭示了当模 m的原根存在时所具有的一些本质特性最后讨论基于离散对数问题的公钥密码体制即ElGamal密码体制，体现了原根在密码学方面的应用2整数指数与原根的定义及其性质2.1整数指数的定义欧拉定理 设m是大于1的整数，(a, m) =1，则a (m)三1(modm).这里的:(m)是个欧拉数，即它在正整数 m上的值等于序列 0，1，2，a -1中与a互质的数的个数这就是说，若(a,m) =1， m 1，则至少存在一个正整数 r，满足ar三1(modm).因此 也存在满足上述要求的最小正整数，故有定义2.1 若m1，(a, m)=1，则使得同余式ar三1(mod m)成立的最

3、小正整数 r叫做a对于模m的指数，记r为ord ma.例2.1找2对于模7的指数解 因为 21 三2(mod7)，22 三4(mod7)，23 三 1(mod7)，所以 ord72 = 3.同样找3对模7的指数.因为1234531 三 3(mod7)，32三 2(mod7)， 33三 6(mod7)，3= 4(mod 7)，35三 5(mod7)，36 三 1(mod 7)，所以 ord73 =6.要求出满足同余式 a*三1(modm)的所有解x，我们可用以下定理：定理2.1若(a,m)=1，m0,则x是ax=1(modm)的解的充要条件是：ord ma | x 第1页共12页xq ordma

4、-ra a/ ord ma-(a)qrra 三 a (mod m)安庆师范学院数学与计算科学学院2009届毕业论文证明 (充分性)若ordma|x，则x=k ordma，其中k为一个正整数，因此xk ord ma / ord ma、ka a(a )由(a, m) =1，知 aordma w1(mod m)，所以 ax 二(aordma)k 三 1(mod m).(必要性)若 ax 三 1(mod m)，则令 x = q ord ma r， 0 _ r ： ord ma，则所以ax三1(mod m)，因此ar三1(mod m).由指数定义知，y =ordma是使a三1(mod m)成立的最小正整

5、数.又因为0二r : ordma，所以r = 0.即x = q ord ma，亦即ord ma | x .例2.2 判断x =10及x =15是否为2x三1(mod7)的解.解 由例2.1知02=3，因为3不被10整除，3|15，因此由定理2.1知，x=10不是 2x =1(mod7)的解，而 x =15 是 2x = 1(mod 7)的解.推论 2.1 若(a, m) =1， m 0 ,则 ord ma | :(m).证明 因为(a, m) =1，由欧拉定理知，a (m1(mod m)，再由定理2.1知，ord ma | (m).例2.3求出7对模9的指数.解 因为小于9且与9互质的正整数有

6、1，2，4, 5，7，8,即“9)=6，又因为6的因子为1，2，3，6,所以由推论2.1知，ordg7只可能是其中一数.又因为71 三 7(mod9)， 72 三 4(mod9)， 73 三 1(mod 9)，所以 ord97 二3.定理 2.2 若(a,m) =1，m 0，则 a 三 aj(mod m)当且仅当 j(mod ordma)，其中i，j都是非负整数.证明 二若i三j(mod ord ma)，不妨设0 - j - i，则i = j kma，k是正整数.ij kord ma, ordma、k ja a(a ) a因为 aordma w1(mod m)，所以第2页共12页安庆师范学院数

7、学与计算科学学院2009届毕业论文i / ord ma、k jja (a ) a = a (mod m).若 a三 aj (mod m)，其中 i _ j，则由(a, m) = 1 知，(aj ,m) = 1 ,因为 a =aj a aj (mod m)，所以 a三 1(mod m)，再由定理 2.1 知，ord ma | (i _ j)，即i = j (mod ord ma).例2.4 设a=3, m=14，由定理2.2可知3.311(mod14)，但39与320不同余于模14.因为(14) =6,5 =11(mod 6)，但9与20不同余于模6.2.2原根的定义我们再来给出原根的定义.定义

8、2.2若(a,m)=1，m . 0，且ordma=(m)，则a称为模m的一个原根.例2.5显然，ord 73 = 6 =(7)，所以3是模7的一个原根.同样，ord?5 = 6 =(7)，所以5也是模7的一个原根.注并不是所有的模m都存在原根.例如：对于模8,小于8且与8互质的数是1，3, 5，7,即(8)=4，而ord81=1，ord83 =ord85 =ord87 =2，所以模8不存在原根.2.3指数与原根的性质.2.3.1关于指数的性质性质2.1若x对于模m的指数是ab，a 0，b 0，则xa对于模m的指数是b .证明 因为(x, m) =1，所以(x , m) = 1，因此x对于模m的

9、指数是存在的.设xa对于模m的指数是：，则(xaT三1(modm) .由定理2.1， ab | ，因而b | .又因为 ab是x对于模m的指数，所以(xa)b = 1(mod m).而：是xa对于模m的指数.由定理2.1，-： | b .其中b，-：都是正整数，所以 b =:.性质2. 2若x对于模m的指数是a，y对于模m的指数是b，并且(a,b) = 1，则xy对于模m的指数是ab.证明 因(x,m) =(y,m) =1,故(xy,m)=1.所以xy对于模m的指数是存在的，且设为，则(xy) =1(mod m).所以 1 = (xy)b = xb yb = x (mod m).由定理 2.1

10、 即得 a |b.第3页共12页t (t, u).证明由性质2.4知，ord mauord ma(u,ordma(m)(u, (m).所以是模 m的安庆师范学院数学与计算科学学院2009届毕业论文又因为(a,b) =1，所以a|、：.同理可证b| 再由(a,b)=1，即得ab|、：.又因为(xy)a(xa)b(yb)a 三 1(mod m).由定理 2.1 知，、；| ab .因为 ab . 0 ,. 0，所以= ab .2.3.2关于原根的性质性质2.3若佝m)=1, m 0，如果a是模m的一个原根，则a1, a2，a (m) 构成模m的简化剩余类.性质2.4 若ord ma =t , u是

11、一个正整数，则 ordm(au)=证明 令 s 二 ord m(au), v = (t, u) , t1v , u = u1v，则(t1, uj = 1 , (au 广三 1(mod m). 因为ord mt,所以at三1(mod m),因此(a/1 =(au1v)v =(aju1 三 1(mod m).由定理 2.1 知，s|t1 .又因为(au)s = aus 三 1(mod m),所以 11 us ,则 t1v | u1vs ,所以t1 | u1S ,又因为(t1,uj=1,所以 t1 |s,因此 s=t1=Z = % u),所以(au)t1 = 1(mod m),即 ordm(au)

12、=t1 =%,u).例 2.6 根据例 2.1 , ord76 ,则由性质 2.3.4 知，ord734 =%4)=_62 = 3.推论2.2若a是模m的一个原根，m为整数，且 m1,则au是模m的一个原根是充要条件是(u, (m) =1 .一个原根 二 ordmau h%m)二(u,(m)=1.3原根存在的条件任给一个模 m,原根是一定存在的吗？在接下来的内容中，我们的主要工作就是确定哪些整数的原根是存在的我们可以验证在前 30个正整数中，模 2 , 3 , 4 , 5 , 6 ,乙9 , 10 , 11, 13 , 14 , 17 , 18 ,19 , 22 , 23 , 25 , 26

13、, 27 , 29 存在原根，而 8 , 12 , 15 , 16 , 20 , 21, 24 , 28 , 30 的原根不 存在.通过观察，在此范围之内，任意的质数都有原根(2 , 3 , 5 ,乙11, 13 , 17 , 19 , 23 ,第4页共12页安庆师范学院数学与计算科学学院2009届毕业论文22329),另外 9 (= 3 ) , 25 ( = 5 ), 27 ( = 3 )有原根，而 6 , 10 , 14 , 18 , 22 , 26 是单质数 的两倍或单质数平方的两倍，剩下2和4也有原根，那么猜想：只有当模 m为2，4，pt, 2pt四者之一时，其中 p为单质数，t为正整

14、数，此模 m才有原根.这是这部分要证明的主要结论在证明此结论之前，先给出引理引理3.1设m 1，(a, m) =1，则m为单质数且a为模m的一个原根的充要条件是ord ma 二 m -1.证明 若m为单质数，a为模m的一个原根，则ordma二(m)二m-1。反之， 若 ordma 二 m -1 ，因 o rm(a| ：(m) ， ord ma _ (m) _ m -1 ，于是 ord ma = (m) = m -1.故a为模m的一个原根， m为单质数.定理3.1若p为单质数，则模 p的原根是存在的.证明 在模p的简化剩余系1, 2,，p1里，每一整数对模 p都有它自己的指数， 从这p -1个指

15、数中取出所有不同的指数，记作-1，: 2， ( 1) 令 =，2，今将证明：(i)有一数g ,它对模p的指数是 ；( ii) 二p-1. 若这两点成立，由引理可得 g便是模p的一个原根.(i )设t =q11q22qJ是的标准分解式，则对每一 s来说，在(1)里一定有一使 得：=aqss，由(1 )的意义知，有一整数，它对模 p的指数是 .设这个整数是x，则由指 数性质2.3.3知，Xs =xa对模p的指数是q：s.故在1, 2,，p-1里有k个数为,x2,， xk，使Xs ( s=1, 2，k)对模p的指数是qss.令g = X1X2Xk，则由指数性质 234 即知g对模p的指数是.(ii)

16、因为 二(s=1, 2,，r )是是因数，而1, 2,，p-1中任一数的指数都在(1)中出现，故x =1(mod p), x = 1,2/ , p -1.即同余式x =1(mod p)至少有p-1个解.则 p -1 .但由推论 2.1 知，:si p-1 ( s = 1,2, ,k),故 | p_1，所以 - p-1，故第5页共12页安庆师范学院数学与计算科学学院2009届毕业论文.二 P -1.定理3.2设g是模p的一个原根，则存在一个整数 t0使得由等式(g - pt0)PJ =1 pu0 所确定的uo不能被p整除，并且对应于这个to的g pto就是模 p的原根，其中是大于1的 任何整数.

17、证明 由欧拉定理即得gp二1(mod p)即有一整数To使得：gpA pTop _1p 2(g pto)=1 p(To -g t pT) =1 pu(2)其中u =To _gpt pT，T是t的整系数多项式显然对任何整数t来说，u 三 To - g pt(mod p)，又由(2)， (gp3p)“， 故此时同余式gpt-To三o(mod p)只有一个解.所以存在一个to 使gpt -To不同余o(mod p)，所以to所对应的uo (即由(g - pto)p =1 puo所确定的uo) 不能被p整除对于满足上述要求的to，我们还有(g pto)p(p4 =(1 pu)p =1 p2u1( 3)

18、其中 u1 二uo c：u： C：pu： -pPu；三u(mod p).所以p不能整除u1，同样可得2(g pto)p(pJ) =(1 P2ujp =1 p3u23(g pto)p(p4) =(1 P3u2)p =1 p4u3( 4)其中 uo三5三上三u3三一 (mod p).即P不能整除us, s=1 , 2, 3，.设g pto对模p：的指数是二，则(g Pto广=1(mod p )( 5)第6页共12页安庆师范学院数学与计算科学学院2009届毕业论文即得(g pto)三 1(mod p)但g - pt0是模p的一个原根，故(p -1) |又由二的定义知| ( p )，即；| (P -1

19、) 故- pr A( p -1)，其中r是1, 2,，:-中某个数，将此结果代入(5)式，再由(2)、(3)及(4)即得1 - prur三 1(mod p -),即prurj =0(mod p :),但 p 不能整除 ur 二，故 pr 三 0(mod p) 则-r，故:-r，即；二(p ).定理3.3设_1,g是模p-的一个原根，则g与g p中的单数是模2 p的一个原根.证明 (i)证每一单数x若适合同余式xrw1(modp：J及xrw1(mod2p)中的任一个 时，则必适合另一个.若x适合同余式x 1(mod 2 p )时，显然x适合xr三1(mod p);反 之，若x适合同余式xr =1

20、(mod p)时，由2不能整除x即得2不能整除xr ,所以 xr 三 1(mod2)，但(2,p:) =1，故得 xr 三1(mod2p：)(ii)若g是单数，则g (p-)三1(mod p ) , gr与1不同余于模 p , 0 ： r 或2p,其中p是单质数.证明 (i)当n亠3时，下列同余式永远成立：22)n na2=1(mod2n),(a,2n) =1(6)iI23因为 a = 2印 1，故 a = 4(a1 1)a11(mod 2 ),第7页共12页安庆师范学院数学与计算科学学院2009届毕业论文22224a2(1 8ti) =1 16(ti 4ti )三 1(mod 24)(n I

21、) 2)(n 2)若 a2三 1(mod 2nl)，则 a2(1 - 2nJ1tn；)2 =1 2n(tn； 2n，t2n；)= 1(mod2n)由归纳法知(6)永远成立.(ii)设 m =2npFp2：2 Pi?是 m 的标准分解式，若(a,m)=1，则(a,2n)= 1,(a, pf ) =1 由欧拉定理及(i)即得a )三 1(mod, i =1, 2,，k .(7)令当 nz2时，a (mod 2n)；沖)n当 n_3时，a2=1(mod2).(8)cp(2n), n 兰 2二 2 (2n), n_3h = ,(P11), ：, ;：(pkk)则由(7)、( 8)及同余基本性质知ah

22、= 1(mod m).上式对所有与 m互质的a都成立.故若h ：(m)，则由原根定义，模 m的原根是不存在的.下讨论，何时h可能等于:（m）.k1当 n3 时，|丨（p）二1 （mP （m）；y2当k 1时，由2不能整除5 , 2不能整除P2知2整除（p；1） , 2整除（p；2），所以（P11）,心门八（P/y（P22）kh：（2n）i 丨（PiB（m）im当 n =2,k =1 时，（2n） =2 , 2| ：（pi：i），而第8页共12页故只有在m =1 jn =2=0k =0n = 0k =1=1四种情形下,=1h才有可能等于 (m)，即安庆师范学院数学与计算科学学院2009届毕业论文

23、只有在m是2,4, p ,2四种数中的一个时，模m的原根才可能存在，故条件的必要性获证(iii )当m=2时，(2)=1，此时1是模2的原根；当m=4时，(4)=2，此时3是原根；当m = p：或2p时，由定理3.1，3.2，3.3知模m的原根是存在的，故充分性获证上结论虽然简单明了， 但由于缺乏模 m存在原根的其他方面特性的沟通，在应用上显得不尽方便，下面将给出关于模m存在原根的其它充要条件，它们从原根与同余方程解的关系这个角度揭示了当模 m存在原根时所具有的一些本质特性，从而提高了应用上的灵活性.定理3.5设m _ 3，模m存在原根的充要条件是同余方程x2三1(mod m)在模m下恰有两解

24、.证明 如果模m存在原根g，那么gig2g (m)构成模m的简化剩余系.设x三gr(modm) (1 乞(m)是同余方程x2三1(mod m)的解，贝U有 g2r三1(modm)，由此推得:(m) |2r .又由m_3知(m)是偶数，于是有(m) r故得2Cp( )Qm)r 创 或(m)，所以同余方程x2=1(modm)在模m下恰有两个解x=g 2或g (m).2反之，如果同余方程 x2三1(modm)在模m下恰有两个解，设 m=2kp/ p了，那么同余方程x2三1(mod m)的解数为2s, 当k=0或1时丁=2卅,当 k=2 时(9)2=当k3时由式(9)及T =2容易推得m = 2 ,

25、4, p-或2 p 再由定理3.4知，模m存在原根.证毕.推论3.1设m3，模m不存在原根的充要条件是同余方程x2三1(modm)在模m下的解数T为4的倍数.Qm)定理3.6设m_3，模m存在原根的充要条件是同余方程x 2三1(modm)在模m下恰有细解.2证明 如果模m存在原根g，那么gg2g (m)构成模m的简化剩余系，容易证明其第9页共12页安庆师范学院数学与计算科学学院2009届毕业论文中蚪(m),2| r)恰好是同余方程 x 2三1(modm)在模m下的丄丄解.反之，如果2他q)(m)同余方程x 2三1(modm)在模m下恰有 (丿解，那么必另有一个整数 a，(a, m)=1，a不2

26、一一、他卄(m)同余1(mod m),使得同余方程x 2三a(modm)在模m下有解，且其解数是 _ ,于是同余2方程x三1(modm)恰有两解x三1或a,再由定理3.5知，模m存在原根.推论3.2 设m_3,模m不存在原根的充要条件是同余方程x 2三1(modm)在模m下有(m)解.4原根的应用EIGmal密码体制EIGmal体制既可用于数字签名，又可以用于加密，它的安全性是基于有限域内计算离散对数的困难性(离散对数问题是指给定一个素数p， Zp的一个生成元：，及一个元素，1 - Zp，寻找整数x，0乞x乞p -2，使得x三l-：(mod p)在ElGmal体制中，要产生一对密钥时，先选择一

27、个素数p和两个随机数g、x，使g和x都小于p然后计算y二gX mod p.公开密钥是y , g和p可以由一群用户共享，秘密密钥 是x.4. 1 EIGmal 签名为签名消息m，首先选择一个随机数 k，1k乞p-2，k与p-1互素，计算ka =g mod p，利用扩展的欧几里德算法，从下式中求出b :m = (xa kb) mod( p -1)签名为一对数a,b，随机变量b保密.要验证签名，只要验证等式yaab mod P = gm mod p是否成立(因为 yaab(mod P)二 gxagkb(mod P)二 gxa kb(mod P)二 gmmodp)每次ElGmal签名或加密都需要一个新

28、的k值，这个值必须随机地选取，如果对手得到了两个用相同的k签名或加密的消息，则即使不知道消息是什么，也可以恢复x.这个体制归纳在表一中.例4.1选择p=11和g=2，秘密密钥x = 8.计算第10页共12页安庆师范学院数学与计算科学学院2009届毕业论文y = g x mod p = 28 mod 11=3公开密钥为y = 3,g = 2, p =11 -为了验证m = 5，选择一个随机数 k = 9.确认gcd (9,10) =1计算a = gk mod p = 29 mod 11=6用扩展的欧几里德算法计算b.m = (ax kb) mod( p -1)5 =(6*8 9* b)mod10

29、解得b = 3，则签名为a = 6和b = 3要验证一个签名，就要确认yaab (mod p) = g m mod p3663 mod11 =25mod11.4.2 EIGmal 加密经过修改的EIGmal算法可以用于加密信息，加密消息m时先选择一个随机数 k，使k与p -1互素，然后计算a = gk mod pb = ykmmod p其中a和b为密文.注意密文的长度是明文的两倍.解密a和b时，计算m = b/ax mod p所以ax = gkx(mod p)因而x _ kx _ xkxk .b/a =ym/a =g m/g = m(mod p)见表二.表一 ElGmal签名表二ElGmal加密公开密钥公开密钥：p 素数(可以由一群用户共享)p 素数(可以由一群用户共享)第11页共12页安庆师范学院数学与计算科学学院2009届毕业论文gp （可以由一群用户共享）g p （可以由一群用户共享）y = g x mod py = g xmod p秘密密钥：秘密密钥：X px c p签名：加密：k随机选取，与p -1互素a （密文）=g mod pa （签名）=gk mod pb （密文）=y mmod pb （签名）满足 m =（xa+kb）mod（ p-1）解密：验证签名：m （明文）=b/axmod p如果y a