1、第五章第五章 原根与指数原根与指数PRIMITIVE ROOT学习目标v 掌握平方剩余与平方非剩余，v 能够算勒让德符号和雅可比符号，能够使用二次互反定律课程内容的设置v 平方剩余与平方非剩余v 勒让德符号v 二次互反定律v 雅可比符号5.0 5.0 问题的引入问题的引入本章围绕的是解高阶方程 xk a(mod m)主要利用的是欧拉定理 a (m)1(mod m)5.1 5.1 阶与原根阶与原根对xk 1(mod m)，(a,m)=1,肯定有解，但最小解？定义5.1.1 n设 ,m 1,(a,m)=1，则使 a r 1(mod m)(1)成立的最小的正整数r，称为a对模m的阶，记为ordm(a
2、)，在不致误会的情况下，简记为ord(a)。n例如：ordm(1)=1,ord2(-1)=1,ordm(-1)=1(m2),ord17(3)=16n注意！如果（a,m）1，则此时ordm(a)=0，以后，在谈到a对模m的指数时，总假定m 1，(a,m)=1 书上将此称为指数，阶更通用 ordm(a)等同的符号是 m(a)，(a)Zma,5.1 5.1 阶与原根阶与原根模10的指数表 a1379ord10(a)1442a123456ord7(a136362模7的指数表 5.1 5.1 阶与原根阶与原根定理5.1.1 阶的基本性质 a n 1(mod m)的充要条件是ordm(a)|n 分析：设n
3、=ordm(a)q+r,0r ordm(a),q,rZ则：a n a ord(a)q+r a r 1(mod m)，因为ordm(a)最小，所以r=0 推论：ordm(a)|(m)若ordm(a)=(m)称a是模m的原根（也写作元根）若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)5.1 5.1 阶与原根阶与原根定理5.1.1 阶的基本性质若a n a l(mod m)，(a,m)=
4、1，则nl(mod ordm(a)分析：不妨设nl，所以a l-n 1(mod m)，所以ordm(a)|l-n 记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-in=ordm(a),与阶的定义矛盾，所以定理成立 特别的：g是原根g0,g1,g m 1是模m的缩系思路：g1,g2,g (m)这（m）个数两两不同余，所以一定组成缩系；另一方面，g1,g2,g (m)是缩系，所以当1l(m)时，gl g (m)，从而ordm(g)=(m)5.1
5、5.1 阶与原根阶与原根定理5.1.1 阶的基本性质 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)记n=ordm(a)，i0,ordm(a i)=s，则 分析：(a i)s 1(mod m)n=ordm(a)|is 则最小的s=所以，当（i,n）=1时，幂后阶不变，此时i的个数为（n）所以，有（n）个a i的阶为n=ordm(a)所以，如果有原根，则原根个数为 (m),(nins sniinin),(|),(snin|),(),(nin 5.1 5.1 阶与原根阶与原根定理5.1
6、.1 阶的基本性质若nm，则ordn(a)|ordm(a)分析：a ordm(a)1(mod m)=a ordm(a)1(mod n)若(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 推论：(m,n)=1，(a1,m)=(a2,n)=1，存在(a,mn)=1 使ordmn(a)=ordm(a1),ordn(a2)(ab,m)=1，(ordm(a),ordm
7、(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)5.2 5.2 原根的存在条件原根的存在条件对于什么样的正整数m，模m的原根是存在?下面的定理不用证明，只需
8、应用定理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是奇素数，1 5.3 5.3 模素数原根的计算技巧模素数原根的计算技巧定理5.3.1n设奇素数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注：性质类似指数、对数，所以
9、有的人将这个称为指数5.4 5.4 指标指标7的指数表填表规则 a那行作乘法，ind a 那行作加法 ind a为1时，对应的a为起始的那个原根a123456ind7a0214535.5 5.5 应用应用EIGamal公钥密码体制n(1)选取大素数p和p的一个原根a，(a,p)=1,1apn(2)随机选取整数d，1dp-1，计算b ad(mod p)；p,a,b为公钥，d为私钥n(3)加密：对0mp，秘密的随机选取整数k,1kp-1,加密后密文为c=(c1，c2),c1 ak(mod p),c2 mbk(mod p)n(4)解密：明文m c2(c1 d)-1(mod p)分析：c2(c1)d
10、mbk(ak d)-1 m adk(ak d)-1 m(mod p)4.2 4.2 勒让德符号（勒让德符号（Legendre）高斯（gauss）引理 现要证这(p-1)/2个数各不相同,只需证ri=p-sj,若ri=p-sj,则ri+sj0(mod p).又因为rita(mod p),sjua(mod p),其中t和u是小于或等于(p-1)/2的两个正整数.于是,(t+u)a(mod p).因为,(a,p)=1,所以(t+u)0(mod p),这是不可能的,因为2t+up-1,故有:而此式左端故!21)(11psprmjjkii)(mod!21112/)1(11ppasrpmmjjkiimmp
11、a14.2 4.2 勒让德符号（勒让德符号（Legendre）定理定理4.2.1 4.2.1 若p是奇素数,则 思路：在高斯引理中,令a=2,则:2,22,23,3,(p-1)/22已在1与p之间,令计算满足p/22kp,有p/4kp/2的k个数则：令 p=8a+r,r=1,3,5,7,则得:该定理表明,若 p1(mod 8),则 2是模p的二次剩余;若 p=3(mod p),则2是模p的二次非剩余.8/)1(212pp,42ppm)2(mod0,1,1,0422rram4.2 4.2 勒让德符号（勒让德符号（Legendre）定理定理4.2.14.2.1 思路2：当1k(p-1)/2时,有:
12、令:则：由高斯引理的证明知ri和p-sj与1,2,(p-1)/2中之一相同(1ik,1jm),因此得:（1）又 （2）,11,ptpkaqtpqkakkkk,11mjjkiisSrRSRtpkk2/)1(1SmpRpp)1(2121812SRqptqpkaappkkpkkpkkpk2/)1(12/)1(12/)1(12/)1(12814.2 4.2 勒让德符号（勒让德符号（Legendre）定理定理4.2.14.2.1（3）-（2）故若a=2 若a奇数 Smpqpappkk2)1(812/)1(12)2(mod2/)1(1pkkqm)2(mod812pm4.3 4.3 二次互反定理二次互反定理
13、定理4.3.1 二次互反定理：数论酵母若p和q是二奇素数,且pq,则有:思路：同理剩下只需证明:（3）2/)1(2/)1(1qppqqp2/)1(12/)1(1111pkpkkpkqqmpq2/)1(11pkpkpqp2)1(2)1(2/)1(12/)1(1qpqkppkqpkpk4.3 4.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,其中,1x(p-1)/2,1y(p-1)/2,即得p|
14、x,q|y,这是不可能的.由于长方型内的整点数为(p-1)/2.(q-1)/2,而l下三角型之整点数为:l上三角形中之整点数为:因此,(3)得证明.2,0q2,2qp0,2p0,0,2/)1(1pkpkq,2/)1(1pkqkp4.3 4.3 二次互反定理二次互反定理推论 若pq3(mod 4),则:否则,这是因为,除非pq3(mod 4)，否则(p-1)(q-1)/4总是偶数,pqqp.pqqp4.3 4.3 二次互反定理二次互反定理对于x2a(mod p),(p,a)=1设设 ,则有则有:当p3(mod 4)时,解为a(p+1)/4.当p5(mod 8)时,a(p-1)/41(mod p)
15、时,a(p+3)/8为(1)的解;当a(p-1)/4-1(mod p)时,a(p+3)/8为(1)的解.思路：当p3(mod 4)时,a(p-1)/21(mod p),即(a(p+1)/4)2 a(mod p).当p5(mod 8)时,先求a=-1的解,由威尔逊定理知:因a(p-1)/21(mod p).a满足:a(p-1)/41(mod p)或a(p-1)/4-1(mod p)时,分别给出(a(p+3)/8)2a(mod p)和:1pa!21p.mod!21122121321!112pppppppp.mod)!21(28/)3(paapp4.3 4.3 二次互反定理二次互反定理对于x2a(m
16、od p),(p,a)=1设设 ,则有则有:p1(mod 8),则同余式(1)有解a(s+1)/2btk,其中s满足:p=2kS+1,2|s,tk0是某个整数.思路:由p1(mod 8),可设p=2kS+1,k3,2|s,所以 所以，1(mod p)故有非负整数 t2=sf(f=0或1)使下式成立:故又有非负整数 t3=sf(f=0或1)使下式成立:因为k是有限整数,故必有一非负整数tk使得:asb2tk1(mod p)于是得:as+1b2tka(mod p)即:(a(s+1)/2 btk)2a(mod p)1pa,1,1pbpa)(mod1),(mod11122pbpasskkska22)(
17、mod121222pbatskk)(mod132322pbatskk4.4 4.4 雅可比符号雅可比符号(Jacobi)中的素数p扩展为合数m 定理4.4.1 设m是一正奇数,pi是素数,(m,a)=1,则:有 称为(Jacobi)符号.性质：设m,n是正奇数.若ab(mod m)和(a,m)=1,则若(a,m)=1和(a,n)=1,则若(a,m)=1和(b,m)=1,则pa,1siipmsiipama1;mbma;mnanama.mabmbma4.4 4.4 雅可比符号雅可比符号(Jacobi)性质：m奇数 思路：则 即故：pi1(mod 8),1is,故则.112/)1(mm.128/)1
18、(2mm.11m,1111111111sjiiisiisiisiipppppmsiipm14mod11siipm12mod2/121 2/)1(2/)1(111111mpsiisiipmsjijisiisiippppm12212122,11111164mod11122siipm2mod8/18/1122siipm4.4 4.4 雅可比符号雅可比符号(Jacobi)定理4.4.2 若m与n是二正奇数,且(m,n)=1,则:思路：令 均为素数,则:而 故：因此：21211nmmnnmjitjjsiiqpqnpm,11kijsitjjipqqpmnnm111tjjsiisitjjiqpqpk1111
19、1211211211212mod1211211mpsii2mod121121nmk21211nmmnnm对于一个明文消息m(0=m n),如果将其加密成m 自身的话,则称m 为RSA 的不动点,也称m为未隐匿的消息。不管加密解密参数如何选取，RSA系统中至少存在九个不动点，即对任意选择的密钥，至少有9个明文消息不会以加密来隐匿，其中有三个是一1,0和1,其余6个明文不动点与参数选取有关，强素数P应当满足以下4个条件:(1)p是一个位数足够长的随机选取的素数;(2)p一1含有一个大的素因子R;(3)p+1含有一个大的素因子S;(4)R-1含有一个大的素因子t4.4 4.4 雅可比符号雅可比符号(Jacobi),1ma1ma,192
