第五章-原根與指標-優(yōu)質(zhì)課件

1、第五章 原根與指數(shù)PRIMITIVE ROOT學習目標掌握平方剩余與平方非剩余，能夠算勒讓德符號和雅可比符號，能夠使用二次互反定律課程內(nèi)容的設(shè)置平方剩余與平方非剩余勒讓德符號二次互反定律雅可比符號5.0 問題的引入本章圍繞的是解高階方程 xk a (mod m) 主要利用的是歐拉定理 a (m) 1 (mod m) 5.1 階與原根對xk 1 (mod m) ，(a,m)=1,肯定有解，但最小解？定義5.1.1 設(shè) ,m 1,(a, m) = 1，則使 a r 1 (mod m) (1) 成立的最小的正整數(shù)r，稱為a對模m的階，記為ordm(a) ，在不致誤會的情況下，簡記為ord(a)。例如

2、：ordm(1)=1, ord2(-1)=1, ordm(-1)=1(m2), ord17(3)=16注意！如果（a,m）1，則此時ordm(a)=0，以后，在談到a對模m的指數(shù)時，總假定m 1，(a, m) = 1 書上將此稱為指數(shù)，階更通用 ordm (a)等同的符號是 m(a)， (a)5.1 階與原根模10的指數(shù)表 a1379ord10(a)1442a123456ord7(a136362模7的指數(shù)表 5.1 階與原根定理5.1.1 階的基本性質(zhì) a n 1 (mod m)的充要條件是ordm(a)|n 分析：設(shè)n= ordm(a)q+r,0r ordm(a),q,rZ則： a n a

3、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.1 階的基本性質(zhì)若a n a l (mod m)，(a, m) = 1，則nl (mod ordm(

4、a) 分析：不妨設(shè)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）個數(shù)兩兩不同余，所以一定組成縮系；另一方面， g1, g2, , g (m)是縮系，所以當1l (m)時， gl g

5、(m) ，從而ordm(g) = (m)5.1 階與原根定理5.1.1 階的基本性質(zhì) 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的個數(shù)為 （n） 所以，有 （n）個a i的階為n= ordm(a) 所以，如果有原根，則原根個數(shù)為 ( (m)5.1 階與原根定理5.1.1

6、階的基本性質(zhì)若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) 分析：設(shè)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 使or

7、dmn(a)= ordm(a1),ordn(a2) (ab, m) =1， (ordm(a),ordm(b)=1則ordm(ab)=ordm(a)ordm(b) 分析：設(shè)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)

8、,所以ordm(ab)|ordm(a)ordm(b)5.2 原根的存在條件對于什么樣的正整數(shù)m，模m的原根是存在?下面的定理不用證明，只需應(yīng)用定理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是奇素數(shù)， 1 5.3 模素數(shù)原根的計算技巧定理5.3.1設(shè)奇素數(shù)p，p-1= ，pi素，若對（a,p）=1滿足 i=1,2,s 則a為p的原根思路：設(shè)ordp(a)=n，則n|p-1，若n1的整，g是其一個原根，(a,m)=1，則存在唯一

9、整數(shù)r使 gr a (mod m) 則r叫做以g為底的a對模m的一個指標，記為r=indga注：性質(zhì)類似指數(shù)、對數(shù)，所以有的人將這個稱為指數(shù)5.4 指標7的指數(shù)表填表規(guī)則 a那行作乘法 ，ind a 那行作加法 ind a為1時，對應(yīng)的a為起始的那個原根a123456ind7a0214535.5 應(yīng)用EIGamal公鑰密碼體制(1)選取大素數(shù)p和p的一個原根a，(a,p)=1,1ap(2)隨機選取整數(shù)d，1dp-1，計算b ad (mod p)；p,a,b為公鑰，d為私鑰(3)加密：對0mp，秘密的隨機選取整數(shù)k,1kp-1,加密后密文為c=(c1 ， c2 ), c1 ak (mod p),

10、 c2 mbk (mod p)(4)解密：明文m c2 ( c1 d) -1 (mod p)分析： c2 ( c1 ) d mbk (ak d) -1 m adk (ak d) -1 m (mod p)4.2 勒讓德符號（Legendre）高斯（gauss）引理 現(xiàn)要證這(p-1)/2個數(shù)各不相同,只需證ri=p-sj,若ri=p-sj, 則ri+sj0(mod p). 又因為rita(mod p), sjua(mod p), 其中t和u是小于或等于(p-1)/2的兩個正整數(shù). 于是,(t+u)a(mod p). 因為, (a,p)=1, 所以(t+u)0(mod p), 這是不可能的, 因為

11、2t+up-1, 故有: 而此式左端故4.2 勒讓德符號（Legendre）定理4.2.1 若p是奇素數(shù),則 思路：在高斯引理中, 令a=2, 則:2,22,23,3,(p-1)/22已在1與p之間, 令計算滿足p/22kp,有p/4kp/2的k個數(shù)則： 令 p=8a+r, r=1,3,5,7, 則得:該定理表明, 若 p1(mod 8), 則 2是模p的二次剩余; 若 p =3 (mod p), 則2是模p的二次非剩余.4.2 勒讓德符號（Legendre）定理4.2.1 思路2：當1k(p-1)/2時, 有:令: 則： 由高斯引理的證明知ri和p-sj與1, 2, , (p-1)/2中之一

12、相同(1ik, 1jm), 因此得:（1）又 （2）4.2 勒讓德符號（Legendre）定理4.2.1（3）-（2）故若a=2 若a奇數(shù) 4.3 二次互反定理定理4.3.1 二次互反定理：數(shù)論酵母若p和q是二奇素數(shù), 且pq, 則有:思路： 同理剩下只需證明:（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上無整點(即二座標為整數(shù)的點).否則有整點(x,y)在l上,則xq-yp=0,其中,1x(p-1)/2, 1y(p-1)/2, 即得p|x, q|y, 這是不可能的.

13、 由于長方型內(nèi)的整點數(shù)為(p-1)/2.(q-1)/2, 而l下三角型之整點數(shù)為: l上三角形中之整點數(shù)為: 因此,(3)得證明.4.3 二次互反定理推論 若pq3(mod 4), 則: 否則, 這是因為, 除非pq3(mod 4)，否則 (p-1)(q-1)/4總是偶數(shù)4.3 二次互反定理對于x2a(mod p), (p,a)=1設(shè) ,則有:當p3(mod 4)時, 解為a(p+1)/4.當p5(mod 8)時, a(p-1)/41(mod p)時, a(p+3)/8為(1)的解; 當a(p-1)/4-1(mod p)時, a(p+3)/8為(1)的解.思路：當p3(mod 4)時, a(p

14、-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)和:4.3 二次互反定理對于x2a(mod p), (p,a)=1設(shè) ,則有: p1(mod 8), 則同余式(1)有解a(s+1)/2btk, 其中s滿足: p=2kS+1, 2|s, tk0是某個整數(shù).思路: 由p1(mod 8), 可設(shè)p=2kS+1, k3, 2|s, 所以 所以， 1(

15、mod p)故有非負整數(shù) t2=sf(f=0或1)使下式成立:故又有非負整數(shù) t3=sf(f=0或1)使下式成立:因為k是有限整數(shù), 故必有一非負整數(shù)tk使得:asb2tk1(mod p)于是得:as+1b2tka(mod p)即:(a(s+1)/2 btk)2a(mod p)4.4 雅可比符號(Jacobi) 中的素數(shù)p擴展為合數(shù)m 定理4.4.1 設(shè)m是一正奇數(shù), pi是素數(shù), (m,a)=1, 則:有 稱為(Jacobi)符號.性質(zhì)： 設(shè)m,n是正奇數(shù). 若ab(mod m)和(a,m)=1, 則若(a,m)=1和(a,n)=1,則若(a,m)=1和(b,m)=1,則4.4 雅可比符號(Jacobi)性質(zhì)：m奇數(shù) 思路 ：則 即故：pi1(mod 8), 1is, 故則4.4 雅可比符號(Jacobi)定理4.4.2 若m與n是二正奇數(shù), 且(m,n)=1, 則:思路：令 均為素數(shù), 則: 而 故： 因此：對于一個明文消息m (0 =