数论算法讲义5章原根与指标

指数根有原根的整数指标(对数)原根及其意义有原根的整数的条件指标及其性质1指数及其基本性质am三1(modm)(一)指数和原根概念ea三1(modm)ee叫做a对模m的指数(或阶)，记作ord全局公开量全局公开量 (二)Diffie—Hellman密钥交换算法q的原根(<q)q生成用户密钥生成用户密钥XA<qXBvqYB三XBmodq交换公开密钥B-A:YBqqA选XA=97,计算B选XB=233,计算=3YA三397三40mod353YB三3233三248mod353 (三)用定义求指数和原根【例1】(按定义求指数和原根)(例1)m=乙贝卩(7)=11三1,23三1,36三1,43三1,56三1,62三1(mod6,3,6,2。列表表示为126a126ordm(a)136362【例2](快速求指数)(例2)m=14=2•7,(14)=6,则11三1,33三—1,53三—1,93三1,113三1,132三1aordm(a)1136569332【例3](无原根的整数)(例3)m=15=3•5, )=8,则12811a412811ordm(a)14244242(四)指数的性质则ddmodm(a))dma法，有d三ordm(a)•q+r,Ovrvordm(a)ar三araordmaq=ad三1(modm)意义：ordm(a)必是(m)的因子，故求ordm(a)只需计算d4,8,16(实际上516不必计算)。【例】求ord33(4)、ord33(5)、ord33(7)的值。可，其中i=1,2,4,5,10。45三1(mod33),55三23(mod33),510三1(mod33),75三10(mod33),710三1(mod33)ordordord2a1----・2ordp(a)=2；当a^p—1(modp)时,ordp(a)=p—1。222(p)=p—1=2•号, —o1知宁，但专是素数，故p1p条件知a2三一1(modp)ordp(a)=2或p-1剩余，不是非剩余)而ordp(a)=2的充分必要条件是a三p—2ord11(1)=1,ord11(3)=ord11(4)=ord11(5)=ord11(9)=5ord11(2)=ord11(6)=ord11(7)=ord11(8)=10,ord11(10)=2(1)若b三a(modm)，则ordm(b)=ordm(a)。(2)ordma=rdm(a)。ordma___ordmabm三am三1(modm)所以ordm(b)Iordma)。其次，aordmb三bordmb三1(modm)所以ordm(a)Iordm(b)。ordm(b)=ordm⑻dmdmaordma由aa1三1(modm)知aa-1ordma-1aordma-1a-1ordma1三1(modm)，从而aordma-1三1(modm)(modm),即卩三1(modm),所以ordm(a)Iordm(a1)k三1(modm)=16。1=a0,a,a2,aOrdmaa三a三a(modm)则由(a,m)=1知ak1三1(modm)1=a0,a,a2,模m两两不同余。由简化剩余系的等价条件知，上述个数(m)【例】(例9)整数{5kIk=0,1,2,…,15}组成模17的简化剩余系 (解)直接计算得0127843594623596【例】设模数m=18,选整数a=5和乙验证定理5.1.2的结论。 (解)(18)=6,直接计算得且知5是模18的原根，从而{5kIk=0,1,2,…,5}组成模18的简-J|_a三a(modm)d三k(modordm(a))k=ordm(a)q+r,0wrvordm(a),q>0又aordma三1(modm),故aad〜ordmaqrraaa三a,a三a(modm)则，设r>r,则有arr三1(modm)，且r-r<ordm(a),矛盾)d=k+ordm(a)tad三akaordmam【例】(例10)21000000三210=100(mod231),因为ord231⑵=30,100000X10(mod30)。ord2002mod31三2=2(mod7)。ordm(ad)= amordma,dadordmadadordmad三1(modm)由定理5.1.1,ordm(a)Idordm(ad)，从而ordmadordmad ordma,dordma,dmmd___dordm=1,故ordma,另一方面，有 dordad dordad三1(modm),ordma,d由定理5.1.1,ordm(ad) amordma,d=2ord175=。旳沁戸ordH5^ord175,28(mod17),所gd是模m的原根(d,(m))=1mgd是原根=(m)(d,(m))=1m,d意义：由一个原根即可得到所有原根。51三5(mod17),53三6(mod17),55三14,(mod57三10(mod17),59三12(mod17),511三11,(mod513三13(mod17),515三6(mod17)【定理5.1.5】(原根的个数)(定理5)设m>1,若m有原根，则其原根个数为((m)) (证)设g为原根，则由定理5.1.2知(m)个数g,而使得(d,(m))=1的整数d共有((m))个，故【推论】(推论)设m>1,且m有原根，设111Pi11P111P211Pk m)=P11P22Pkk,i>0,i=1,2，…,k则当(a,m)=1时，a是模m的原根的概率为mm再由欧拉函数的计算公式得mm’1’1’1211(解)首先，(25)=20,((25))=(20)=&故25计算25三7(mod25),210三24三-1(mod25),所以220的简化剩余系为{1,3,7,9,11,13,17,19}由定理213三17,217三22,219三13(mod17)3【定理(ordm(a),反之亦然ordm(a))=1,则ordm(ab)=ordm(a)ordm(b)11111111又aordmbordmab-aordmbordmabbordmordmabordbordabm三ordbordabm故ordm(a)Iordm(b)ordm(ab)，而(ordm(a),ordm(b))=1，因此ordm(a)Iordm(ab)。同理可证ordm(b)Iordm(ab)。再利用(ordm(a),ordm(b))=1,得ordm(a)ordm(b)Iordm另一方面,abordmaordmb_aordmaordmbbordmbordma三1(modm)从而ordm(ab)ordm(a)ordm(b)ordm(ab)反之,若=ordm(a)ordm(b)ordm(ab)ordma,ord=ordm(a)ordm(b)，那么abmbordma,ordmbbordma,ordmbmodm)因此,ordm(ab)I[ordm(a),ordm(b)]ordm(a)ordm(b)[ordm(a),ordm(b)]ordm(a)ordm(b)>[ordm(a),ordm(b)]所以ordm(a)ordm(b)=[ordm(a),ordm(b)]所以(ordm(a),ordm(b))=1rd2i,其中i=1,3,9,11,13,17,19,23,27,29,31,33,37,39,41,43,47,51,53,57,59,61,67,69么，因为ord19(2)=18,且ord19(5)>1,故ord19(2)•ord19(5)>ord19(10)，从而说明rd(验证,ord19(5)=9，故(ord19(2),ord19(5))=(18,9)an=1，那么(1)若n|m,则ordn(a)Iordm(a)(2)若(m,n)=1,则ordmn(a)=[ordm(a),ord“(a)](证)(1)由ordm(a)的定义知aordma三1(modm)。(2)由(1)知从而由最小公倍数性质知[ordm(a),ordn(a)]ordmn(a)。aordma,ordna_三joradn(m,n)=1aordn(modn)时有,aordma,ordna=1(modmn)则ordpq(a)=[ordp(a),ordq(a)]end(1<d<ordpq(a))，使得ed=1(modordpq(a))且对于c=ae(modn),有a=cd(modn)=1。所以d=e1(modordpq(a))存在，即ed=1+kordpq(a)ppkorpa1kordpqaaorpaordpqakordpqak—ordpqa 即aed三a(mod同理有aed三a(q)所以aed三a(modn)因此.-J12k则ordm(a)=m=25(解)已知(33,100)=1,且100=2252。分别求ord4(33)和25(33)。ord4(33)=ord4(1)=1ord25(33)=ord25(8)=20所以ord100(33)=[ord4(33),ord25(33)]=[1,20]=20ord4(7)=ord4(3)=2ord25(7)=4所以ordioo(7)=[084(7),ord25(7)]=[2,4]=4【定理5.1.8】(定理8)设m,n都是大于1的整数， ordmn(a)=[ordm(aj，ord“(a?)]xa1modm (证)考虑同余方程组xa2modn由中国剩余定理，方程组有唯一解x三a(modmn),则a即为所求。因为由性质1(i),有ordm(a)=ordm@1),ordn(a)=ordn@2)14,求满足ord1127(a)=[ord11(7),ord27(14)]的a。x14mod27x三95(mod11•27=297),即a=95验证：ord1127(95)=90,ord11(7)=10,ord27(14)=18[ord11(7),ord27(14)]=[10,18]=90=ord1127(95)abordmordm (b)]成立。例如ordio(21)=4=[4,4]=[ordio(3),ord卩⑺]有mambm1,则ordm(c)=[ordm(a),ordm(b)]足ordm(a),vordm(b)，且(u,v)=1[ordm(a),ordm(b)]=uv则ordmordma,s=m1muordmordm=ordba,ordb,ma—u=b=bvordm(as)= damordma,s,,tordmbordm(b)=Lordmb,t=v,ordm(asbt)=ordm(as)ord口⑹)=uvb(3631)=3630=2•3•5•11222ord3631(2)=605=5•11,ord3631(3)=1210=2•5•11ord3631(5)=363=3•112,ord3631(6)=1210=2•5•1122ord3631(7)=33=3•11,0旳3631(10)=1815=3•5•11ord3631(11)=330=2-3-5-11,ord3631(12)=1210=2-5-112ord3631(13)=1815=3•5•112,ord3631(14)=1815=3ord3631(15)=3630=2•3•5•112,ord3631(17)=1212•5•112由定理5.1.9,取a=3,b=5以及u=1210,v=3,这时，s=1,t=112,c=asbt=315121三2623(mod3631)ord3631(2623)=[ord3631(3),ord3631(5)]=[1210,363]=0还可利用a=11,b=13并选u=2•3•5,v=112,得s=tc2-1051^3364(mod3631)也为原根。条件【定理521】(定理1)设p为奇素数，则模p的原根存 (证)(构造性)记er=ordp(r),1<r<p—1ep1]g三1(modp)g三1(modp)故eI(p)=p—1,xe三1(modp)有p—1个解x=1,2，…,p—1(modp) (定理3.4.4:同余方程fX=aa1xa0三0(modp)的解数不超过anxnan1xn1其次数(an0(modp))【推论】(推论)设p为奇素数，d是p—1的正因子，则【定理5.2.2】(定理2)设g是模p的一个原根，则g或g【定理523】(定理3)设p为奇素数，则对任意正整数a,模33=27,34=81,…的原根。54=625,…的原根。pggp的奇数是模m=2p的一个原根。2=2,2+9=11【定理525】(定理5)设a是一个奇数，则对任意a》3,有a22=a2三1(mod2) (本定理说明说明ord2(a)I22)【定理526】(定理6)设a》3,则ord2(5)=2/2=22amqi工1(modm),i=1,2，…,k意义：给出了一个找原根的方法(解)(m)=(41)=40=23•5,q1=2,q2=5,mq1=20,mq2=8,故只需验证g8,g20三1?(mod41)420=240三1(mod41),4不是原根。58三18,520三1(mod41),5不是原根。68三10,620三40=—1(mod41),6是原根。1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39共有((41))=(40)=16个数，那么原根为61三6,63三11,..,639三7(mod41)640=143=1+41•3(mod412),4740三1518三1+41•37(mod412)即640工1(mod412),4740工1(mod412)所以6和47都是模1681的原根(因(412)=1640=4140)。6+412=1687和47是模2•412=3362的原根。p模数p而言，指数为d的数恰有个(d)。：xnamodma,m)=1xx(m)),使得g三y(modm)【例1】：m=10,(10)=4,其简化剩余系为{1,3,乙【例2]:m=18,(18)=6,其简化剩余系为 {1,5,7,11,13,17}。由(6)=2知，模18有两个原根5和11。选X=1,2,3,4,5,65X三5,7,17,13,11,1(modm)是18的简化剩余inda。指标也称为对数或离散对数，也记为r=logga。11314151216431571796810119ra514528536再由上表构造离散对数表334526131219101110711a=logga131415451481798263(三)离散对数的性质r三indga(mod(m))因为(a,m)=1,故m从而gr-indga三1(modm)(m)Ir—indga故r三indga(mod(m))而ind52=6,故38三6=ind52(也可以说有同一真数的对数有无穷多)=1,则indgl三0(mod(m)),indgg三1(mod(m))g0三1(modm),g1三g(modm)(ai,m)=1(i=1,2,…,n),则indga1a2an三indga1+…+indgan(mod特别地indgan三nindga(mod(m))piai三gi(modm),i=1,2，…,na1a2an三gr1r2rn(modm)indgaaanr+r2+…+rn(mod(m))r的所有整数全体是模m的一个简化剩余类。■rr==indggr,(g,m)1rindga=ra三g(modm) ,53,…) (也可以说有同一对数的真数也有无穷多)【例】(例2)作模41的指标(即离散对数表)表。 (解)已知6是模41的原根，计算6r(mod41)得以6为底的离散对 位置为对数y)499749975756161280230238834435226420由此可构造反对数表(即指数函数表，y=6X):0012345678906143252349187(解)查上例所给离散对数表，可得计算离散对数的复杂度：求离散对数是困难问题。即已知模数od原方程变为x三6y(mod41)5y三30(mod40=(41))(2)即y三6(mod8)故(2)的解为y三6,14,22,30,38(mod40)x三6y=66,614,622,630,638ind(mod41)原方程变为6是原根，故有x三6y(mod41)67y三630(mod41)解之，得y三10(mod40)故原方程有唯一解x三610三32(mod41)ind(mod41)原方程变为6是原根，故有x三6y(mod41)68y三630(mod41)8y三30(mod40=(41))此方程无解，故原方程无解。1,则同余方程xn三a(modm)(3)则分别存在非负整数u,r，使得xo三gu(modm),a=gmodm但要注意取对数后模数变为(m))(n,(m))Ir=indga反之，若(n,(m))Ir=indga,则方程(4)有解y三u(mod(m))且解数为d=(n,(m))。因此，方程(3)有解解数为(n,(m)))■.目口」宵匚m/d—rm■dmr：'d—彳indga,即卩dr，所以a'=g三g=1(m)r——=-(m)dd(解)d=(n,(m))=(8,(41))=(8,40)=8(解)d=(n,(m))=(12,(41))=(12,40)=4查表得ind6(37)=32求等价方程，原方程两边同时取对数，得12ind6x三32(mod40)(5)处n=12,r=32)利用同余性质有为方程(5)的解为查离散对数的反函数表(即指数函数表)得原方程的解为x三66,616,626,636三39,18,2,23amorda【定理536】(定理6)设m>1,g是模m的一个原根，则模m的简化剩余系中，阶是e的整数共有(e)个。特别地,原根共有((m))个。 (证)因m有原根g,由定理5.1.3,知a=gd的阶为ordmgordmg,d=e,即m,d ((m),d)=—e令d=d