第五章-原根与指标

第五章原根与指数PRIMITIVEROOT学习目标掌握平方剩余与平方非剩余，能够算勒让德符号和雅可比符号，能够使用二次互反定律课程内容的设置平方剩余与平方非剩余勒让德符号二次互反定律雅可比符号5.0问题的引入本章围绕的是解高阶方程xka(modm)主要利用的是欧拉定理a(m)1(modm)5.1阶与原根对xk1(modm)，(a,m)=1,肯定有解，但最小解？定义5.1.1设,m1,(a,m)=1，则使ar1(modm)(1)成立的最小的正整数r，称为a对模m的阶，记为ordm(a)，在不致误会的情况下，简记为ord(a)。例如：ordm(1)=1,ord2(-1)=1,ordm(-1)=1(m2),ord17(3)=16注意！！如果（a,m）1，则此时ordm(a)=0，以后，在谈到a对模m的指数时，总假定m1，(a,m)=1书上将此称为指数，阶更通用ordm(a)等同的符号是m(a)，(a)Zma,5.1阶与原根模10的指数表a1379ord10(a)1442a123456ord7(a136362模7的指数表5.1阶与原根定理5.1.1阶的基本性质①an1(modm)的充要条件是ordm(a)|n分析：设n=ordm(a)q+r,0≤rordm(a),q,r∈Z则：anaord(a)q+rar1(modm)，因为ordm(a)最小，所以r=0推论：ordm(a)|(m)╬若ordm(a)=(m)称a是模m的原根（也写作元根）②若ab(modm)，(a,m)=1，则ordm(a)=ordm(b)分析：aord(a)bord(b)aord(b)bord(a)1(modm),所以ordm(a)|ordm(b),ordm(b)|ordm(a),所以ordm(a)=ordm(b)5.1阶与原根定理5.1.1阶的基本性质③若anal(modm)，(a,m)=1，则nl(modordm(a))分析：不妨设n≤l，所以al-n1(modm)，所以ordm(a)|l-n④记n=ordm(a)，则a0,a1,,an1对模m两两不同余。分析：用反证法。若有0ijn1，使得aiaj(modm)，则由(a,m)=1得到aji1(modm)，这与j-in=ordm(a),与阶的定义矛盾，所以定理成立╬特别的：g是原根=g0,g1,,gm1是模m的缩系思路：g1,g2,,g(m)这（m）个数两两不同余，所以一定组成缩系；另一方面，g1,g2,,g(m)是缩系，所以当1≤l≤(m)时，gl≡g(m)，从而ordm(g)=(m)5.1阶与原根定理5.1.1阶的基本性质⑤a-1a1(modm)，则ordm(a)=ordm(a-1)分析：(a-1a)n1(modm)则(a-1)n1(modm)=an1(modm)⑥记n=ordm(a)，i0,ordm(ai)=s，则分析：(ai)s1(modm)=n=ordm(a)|is==则最小的s=所以，当（i,n）=1时，幂后阶不变，此时i的个数为（n）所以，有（n）个ai的阶为n=ordm(a)所以，如果有原根，则原根个数为((m))),(ninssniinin),(|),(snin|),(),(nin5.1阶与原根定理5.1.1阶的基本性质⑦若nm，则ordn(a)|ordm(a)分析：aordm(a)1(modm)=aordm(a)1(modn)⑧若(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;as1(modm),as1(modn)=as1(modmn)=t|s推论：(m,n)=1，(a1,m)=(a2,n)=1，存在(a,mn)=1使ordmn(a)=[ordm(a1),ordn(a2)]⑨(ab,m)=1，(ordm(a),ordm(b))=1则ordm(ab)=ordm(a)ordm(b)分析：设aordm(b)ordm(ab)aordm(b)ordm(ab)bordm(b)ordm(ab)(ab)ordm(b)ordm(ab)1(modm)=ordm(a)|ordm(b)ordm(ab),同理，ordm(b)|ordm(a)ordm(ab)所以，ordm(a)ordm(b)|ordm(ab)另一方面(ab)ordm(b)ordm(a)1(modm),所以ordm(ab)|ordm(a)ordm(b)5.2原根的存在条件对于什么样的正整数m，模m的原根是存在?下面的定理不用证明，只需应用定理5.2.1若p奇素，则原根存在定理5.2.2若p奇素，g是模p的一个原根，则g或g+p是模p2的原根，若g是模p2的原根，则g是模p的原根，定理5.2.3模m有原根的必要条件是m=2，4，p或2p，其中p是奇素数，15.3模素数原根的计算技巧定理5.3.1设奇素数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=piu即与条件矛盾，所以n=p-1ieisip1)(mod11paipp)(mod11paanuppi5.4指标定义5.4.1设m1的整，g是其一个原根，(a,m)=1，则存在唯一整数r使gra(modm)则r叫做以g为底的a对模m的一个指标，记为r=indga注：性质类似指数、对数，所以有的人将这个称为指数5.4指标7的指数表填表规则a那行作乘法，inda那行作加法inda为1时，对应的a为起始的那个原根a123456ind7a0214535.5应用EIGamal公钥密码体制(1)选取大素数p和p的一个原根a，(a,p)=1,1ap(2)随机选取整数d，1dp-1，计算bad(modp)；p,a,b为公钥，d为私钥(3)加密：对0mp，秘密的随机选取整数k,1kp-1,加密后密文为c=(c1，c2),c1ak(modp),c2mbk(modp)(4)解密：明文mc2(c1d)-1(modp)分析：c2(c1)dmbk(akd)-1madk(akd)-1m(modp)4.2勒让德符号（Legendre）高斯（gauss）引理现要证这(p-1)/2个数各不相同,只需证ri=p-sj,若ri=p-sj,则ri+sj0(modp).又因为rita(modp),sjua(modp),其中t和u是小于或等于(p-1)/2的两个正整数.于是,(t+u)a(modp).因为,(a,p)=1,所以(t+u)0(modp),这是不可能的,因为2≤t+u≤p-1,故有:而此式左端故!21)(11psprmjjkii)(mod!21112/)1(11ppasrpmmjjkiimmpa14.2勒让德符号（Legendre）定理4.2.1若p是奇素数,则思路：在高斯引理中,令a=2,则:2,2·2,2·3,…,3,(p-1)/2·2已在1与p之间,令计算满足p/22kp,有p/4kp/2的k个数则：令p=8a+r,r=1,3,5,7,则得:该定理表明,若p1(mod8),则2是模p的二次剩余;若p=3(modp),则2是模p的二次非剩余.8/)1(212pp,42ppm)2(mod0,1,1,0422rram4.2勒让德符号（Legendre）定理4.2.1思路2：当1≤k≤(p-1)/2时,有:令:则：由高斯引理的证明知ri和p-sj与1,2,…,(p-1)/2中之一相同(1≤i≤k,1≤j≤m),因此得:（1）又（2）,11,,ptpkaqtpqkakkkk,,11mjjkiisSrRSRtpkk2/)1(1SmpRpp)1(2121812SRqptqpkaappkkpkkpkkpk2/)1(12/)1(12/)1(12/)1(12814.2勒让德符号（Legendre）定理4.2.1（3）-（2）故若a=2若a奇数Smpqpappkk2)1(812/)1(12)2(mod2/)1(1pkkqm)2(mod812pm4.3二次互反定理定理4.3.1二次互反定理：数论酵母若p和q是二奇素数,且p≠q,则有:思路：同理剩下只需证明:（3）2/)1(2/)1(1qppqqp2/)1(12/)1(1111pkpkkpkqqmpq2/)1(11pkpkpqp2)1(2)1(2/)1(12/)1(1qpqkppkqpkpk4.3二次互反定理定理4.3.1作为(0,0),(0,q/2),(p/2,0),(p/2,q/2)为顶点的长方型连接(0,0)和(p/2,q/2)之对角线l,则l上无整点(即二座标为整数的点).否则有整点(x,y)在l上,则xq-yp=0,其中,1≤x≤(p-1)/2,1≤y≤(p-1)/2,即得p|x,q|y,这是不可能的.由于长方型内的整点数为(p-1)/2.(q-1)/2,而l下三角型之整点数为:l上三角形中之整点数为:因此,(3)得证明.2,0q2,2qp0,2p0,0,2/)1(1pkpkq,2/)1(1pkqkp4.3二次互反定理推论若pq3(mod4),则:否则,这是因为,除非pq3(mod4)，否则(p-1)(q-1)/4总是偶数,pqqp.pqqp4.3二次互反定理对于x2a(modp),(p,a)=1设,则有:①当p3(mod4)时,解为±a(p+1)/4.②当p5(mod8)时,±a(p-1)/41(modp)时,±a(p+3)/8为(1)的解;当±a(p-1)/4-1(modp)时,±·a(p+3)/8为(1)的解.思路：①当p3(mod4)时,a(p-1)/21(modp),即(a(p+1)/4)2a(modp).②当p5(mod8)时,先求a=-1的解,由威尔逊定理知:因a(p-1)/21(modp).a满足:a(p-1)/41(modp)或a(p-1)/4-1(modp)时,分别给出(a(p+3)/8)2a(modp)和:1pa!21p.mod!21122121321!112pppppppp.mod)!21(28/)3(paapp4.3二次互反定理对于x2a(modp),(p,a)=1设,则有:③p1(mod8),则同余式(1)有解±a(s+1)/2·btk,其中s满足:p=2k·S+1,2|s,tk≥0是某个整数.思路:由p1(mod8),可设p=2k·S+1,k≥3,2|s,所以所以，±1(modp)故有非负整数t2=sf(f=0或1)使下式成立:故又有非负整数t3=sf(f=0或1)使下式成立:因为k是有限整数,故必