初等数论ppt(12)第六章---指数与原根

初等数论-第六章指数与原根01()11().,,,.4mmmmmmggggm引进并讨论指数的概念和性质.指数是刻画模的简化剩余系中的元素特征的一个量;指数等于的元素称为是模的原根讨论模存在原根的充要条件及求原根的算法;当模存在原根时,就给出了模的简化剩余系,给出了一个简单且便于研究的形式.3指标、指标组的概念与性质离散对数密码体制2本章内容1,(,)1,1(mod).1,(,)1,1(mod),.mdmamammamdam由欧拉定理知：若则也就是说,若则存在一个正整数满足因此也存在满足上述要求的最小正整数§1指数11,(,)1.1(mod)(),()()()dmmammamamdaamamm定义设使成立的最小正整数称为或阶把它记作.定义2当时,称是模的原根，简对模的指称数的原根.§1指数7.m例1,(7)=6,求模7的指数和原根231025.1535.93.82.mmmm例2,(10)=4,求模10的指数和原根例3,(15)=8,求模15的指数和原根例4,(9)=6,求模15的指数和原根例5,(8)=4,求模8的指数和原根a-3-2-11233621367a221(mod),(,)1,()().1(mod)()0(mod()).()()()23.(,)1,(mod),(mod()).lmmdmmlmkhmbamambaamaddaamalamaamkha性质若则性质2若成立,则即性质3,,性质4若则()1012361234,)1,,,,((()()2924,28,21mod9.29622mod9,24mod9,28mod9,27mod9,mammamaaaamamammm性质5若(则这)个数对模两两不同余.特别地,当是模的原根时，即)时,这个数是模的一组既约剩余系.例是模的一个原根,这是因为由性质知,的幂的前个构成模9的一个既约剩余系.它们是5625mod9,21mod9.11111(mod)(().1(mod))1(mod)mmddaamaamaaamam性质6设是对模的逆,即我们有)证这由成立的充要条件是(立即推出.*'**'*'**.()()(),'/(,),*().1(mod),1(mod),()((3,.',,(,)(,)(()),)kmmmmkmmkkmkmamaakaamamkkakkaak性质7设是非负整数,则有此外,在模的一个既约剩余系中,至少有（）个数对模的指数等于.证记由定义知因而由性质2得由第一式得因而所以)=',,())1()(),5.kmmmkaaa即式(3)成立.当(时,由此及性质证明了结论''''''''()()()((())1.'(),''(),(),[(),()].()()(mod),''',','''.()()(mod),''',mmmmmmmmmmababababababababamababbm性质8的充要条件是),证设我们有1所以,由此及()=1推出同样,有充1所以,分性:由'''','''''.()1(mod),''''.'''.()1(mod),.''','''''',',''abmabm必此及()=1,推出此外,显然有所以,因此,由得另一方面有由此及就推要性：出即()=1.121212121212****1212*(i),()();(ii)(,)1,()[(),()].(4)(i)2()[(),()].1(mod),1,2.(,)11(mod).2().nmmmmmmmmmjmmnmaammaaaaaaamjmmamma性质9若则若则有证可由性质直接推出.由(i)即得,这里另一方面,显然有由此及推出因而由性质推出所以(4)式成立.1212101011111100000()[(),()],,()[(),,()].()[(),,()].2,()[2,(),,()](),0,0,11,22,srrmmmmssmmmmsrjcmraaammmmmaaaammmpppappmc推广为:若两两即约,,则由此及性质3推出：特别地,当是不同的奇素数,我们有其中1057153(2)[(2),(2)][6,4]12.例：1212112212121211211212,.,((),()].(mod),(mod),(mod),((((mmmmmmmmmmaaaaaaxamxamxammaaaa性质10设()=1那么,对任意的,必有使得)=[证考虑同余方程组由孙子定理知,这同余方程组有惟一解:显然有)=),)=).由此从性质9就推出所要结论.101010101010101010101010m((),()](33(3),(3)]4.(37(7),(9)]4.(39(3),(9)]4,(79(7),(9)]4.mmmabab对于模来说,不一定有)=[成立.例如：)=2[)=1[但有)=4=[)=4=[''''''''',,((),()].'(),'(),[',''].',''''','''''',','')1,'''.7()',()''.()()()'mmmmmmmmmmabccababababab性质11对任意的一定存在使得)=[证设一定可以把作分解：使得(由性质知这样,由性质8推出'''''.cab因此取就满足要求.0011111,2,4,,2,2(3),2(2,1),2(0,2),(10)1(1).()()(),rrrrjjmmpppmmpprpprpjrmmmmm性质12模存在原根的必要条件是：其中是奇素数.证当不属于上式列出的情形时,必有或其中为不同奇素数,设由式给出,容易验证,当属于式(10)列出的任一情形时,必有由此知,这时模没有原根.1,2,4,,2,1,().mmpppppdppdpd定理1模有原根的充要条件是其中是奇素数,1.定理2模是素数,则模必有原根.事实上,对每一正整数在模的一个简化剩余系中恰有个数对模的指数为§2原根11111,,()()().1,ppppggppgpgpgpgpppgpgrpprgp定理3设为奇素数.那么,对任意的1,模必有原根.事实上,存在使得对所有的是模模2的公共的原根.(i)若是模(1)的原根,则一定是模的原根.(ii)若是模的原根,则必有或(iii)当是奇素数,若是模的原根,且有则是所有模(1)|''''',0,1,,1.pgpggpgggtptpgp的原根.(iv)当是奇素数,若是模的原根且为奇数(若是偶数,则以代),那么有(v)由(iii)和(iv)立即推出是模(1)的原根.3,23pppppp如何求原根是个困难问题.首先要去求模的原根,然后依次按照定理的证明中方法求模2的原根,但求模的原根没有一般的方法,只能对具体的素数按原根的定义逐个数去试.例1求的原根.例2求模41的原根.1(1)/01()11,,.1(mod),1,,.1.,,,,1,2,4,,2(),jspqmppqqgpgpjsmmggggmpppm定理4设是奇素数,的所有的不同的素因数是那么,是模的原根的充要条件是定理5设模的既约剩余系能表为：这里为某一整数,当且仅当是奇素数,1即模有原根.01()1,1,,,.,(,)1,(mod),0().,()mmggggaamagmmmgmm当模有原根时它的既约剩余系可表为也就是说,对任一必可惟一地表为:这表明当模有原根时,通过原根模的既约剩余系与模的完全剩余系之间可建立一一对应的关系.§3指标、二项同余方程,1,(,)1.(mod),0()(),()().mggmgamagmmamgaaa定义设模有原根我们把中的称为是对模的以为底的指标,记作当不会混淆时简记作或,,,,,()()()()(,)1.(mod),()(mod()),(,)1,()()()(mod()).()(),(mod)hmgmgmgmgmgababgmamgamhamgmabmababmccabgggm性质1设是模的原根,若则有且反过来也成立.性质2设是模的原根,则有证：记我们有32231,,,1,2,3,,,,(,)1.()()()(mod()).(),(),().(mod),(mod),(mod),(mod).1,()mgmgmgmgmgmgmgmgggmamagamagaagmggmagmagmagg性质3设是模的两个不同的原根,我们有证:设由此及性质证得.特别地,取()1(mod())3.gm性质刻画了对不同原根的指标之间的关系以上性质表明：通常对数的运算规则,对指标的运算也成立.,(,)1.()()/((),()).(),().mmggmamamammdmmdmdm性质4设是模的原根,我们有由此推出,当有原根时,对每个正除数在模的一个既约剩余系中,恰有个元素对模的指数等于特别地,恰有(())个原根.01()1,,,,()()/((),())..mjmmgmgggggmmamam当已知模的一个原根时,我们通过依次计算中的对模的绝对最小剩余或最小正剩余,就可得到模的绝对最小既约剩余系或最小既约正剩余系的每个元素的指标，由此从得到指数把所得这些结果，按指标的大小顺序或既约剩余系的大小顺序来列表这种表通常称为指标表.例1构造模23以原根5为底的指标表.2,(mod).12,(,)1,2.(mod)12,(,)1,(,)1,(mod)(,())(),()nnnnxammmamnxamamnamnmamammxamamnnmaa设我们把同余方程称为模的二项同余方程定义设如果同余方程有解,就称是模的次剩余,如果无解,就称是模的次非剩余.定理设及模有原根g.那么,同余方程有解,即模的次剩余的充要条件是这里,()g(,()).mgaamnm是对模的以为底的指标.有解时恰有个解8()/(,())41(mod)2,2.()/(,()).3,2.1(mod),(,()).mnmxmnmmnmnmmnamnamnm例1解同余方程23定理设有原根那么,在模的一个既约剩余系中,模的次剩余恰有个定理设有原根那么,模的次剩余,即二项同余方程有解的充要条件是成立有解时有个解离散对数Diffie和Hellman在1976年提出的Diffie-Hellman密钥交换协议，是一个典型的密钥协商协议；允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程算法的安全性依赖于计算离散对数的难度生成元2-12.,mod,mod,,mod,1-1,,.523.qqaqaqaqqaq1.离散数学数论对于一个素数如果数是不同的整数并且以某种排列方式组成了从到的所有整数则称整数是素数的一个本原元也称为生成元或原根例如是的原根离散对数的概念对于一个整数b和素数q的一个生成元a，可以找到一个唯一的指数i，使得：成立，则指数i称为b的以a为底数的模q的离散对数。)10(m