《數(shù)論算法》教案-5章(原根與離散對(duì)數(shù))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)原根與離散對(duì)數(shù)內(nèi)容整數(shù)的階原根有原根的整數(shù)離散對(duì)數(shù)（指標(biāo)）要點(diǎn)原根及其意義有原根的整數(shù)的條件離散對(duì)數(shù)及其性質(zhì)階及其基本性質(zhì)準(zhǔn)備知識(shí)：歐拉定理：m1，(a, m)1，則1（mod m）問題：是否是使得上式成立的最小正整數(shù)？該最小正整數(shù)有何性質(zhì)？階和原根概念【定義5.1.1】設(shè)m1，(a, m)1，則使得1（mod m）成立的最小正整數(shù)e叫做a對(duì)模m的階（或指數(shù)），記作(a)。若a的階e，則a叫做模m的原根。應(yīng)用：DiffieHellman密鑰交換算法公鑰算法的核心：僅依賴

2、公開信息不足以對(duì)算法構(gòu)成威脅；掌握私鑰者可輕易獲得信內(nèi)容。全局公開量q 素?cái)?shù) q的原根（q）生成用戶密鑰用戶A選擇秘密的 q計(jì)算公開的 （mod q）用戶B選擇秘密的 q計(jì)算公開的 （mod q）交換公開密鑰AB： BA： 生成公共密鑰K用戶A計(jì)算 K（mod q）用戶B計(jì)算 K（mod q）說明：K（mod q）例：素?cái)?shù)q353，原根3A選97， 計(jì)算40 mod 353B選233， 計(jì)算248 mod 353A與B交換A計(jì)算密鑰 K160 mod 353B計(jì)算密鑰 K160 mod 353用定義求階和原根【例1】（按定義求階和原根）m7，則(7)6。且1，1，1，1，1，1（mod 7）故

3、對(duì)模數(shù)7而言，1，2，3，4，5，6的階分別為1，3，6，3，6，2。列表表示為a123456(a)136362因此，3，5是模7的原根?！纠?】（快速求階）m1427， (14)6，則1，1，1，1，1，1（mod 7）列表a13591113(a)166332故3，5是模14的原根?！纠?】（無原根的整數(shù)）m1535， (15)8，則a12478111314(a)14244242故模數(shù)15沒有原根。同理，可知模數(shù)m9時(shí)，其原根為2，5；而整數(shù)8則沒有原根。也可以計(jì)算驗(yàn)證5是模3、6、9、18的原根。階的性質(zhì)【定理5.1.1】設(shè)m1，(a, m)1，d為正整數(shù)，則1（mod m） (a) d即

4、d0（mod (a)）（證）充分性：設(shè)(a) d，則dk(a)，從而1（mod m）必要性：反證：若1且(a) d，則由歐幾里得除法，有d(a)qr， 0r(a)從而1（mod m）與(a)的最小性矛盾。【推論1】(a) (m)。意義：(a)必是(m)的因子，故求(a)只需計(jì)算，其中i(m)?！纠?】（用定理5.1.1結(jié)論快速求階及原根）（例7）求(5)的值。（解）(17)16，只需計(jì)算（mod 17），其中d1，2，4，8，16（實(shí)際上不必計(jì)算）。5，8，134，161（mod 17）所以，(5)16，即5是模17的原根?！纠?】求(4)、(5)、(7)的值。（解）(33)20。只需計(jì)算、（

5、mod 33）（i1, 2, 4, 5, 10）。1（mod 33）；23（mod 33），1（mod 33）；10（mod 33），1（mod 33） (4)5，(5)10，(7)10【推論2】設(shè)p是奇素?cái)?shù)，也是奇素?cái)?shù)，pa，則（1）若a是模p的二次剩余，則a不是p的原根，且當(dāng)a1（mod p）時(shí)，(a)1；當(dāng)a1（mod p）時(shí)，(a)；（2）若a是模p二次非剩余，則當(dāng)ap1（mod p）時(shí)，(a)2；當(dāng)ap1（mod p）時(shí)，(a)p1。（3）此時(shí)，p有1個(gè)原根。（4）當(dāng)2為偶素?cái)?shù)時(shí)，必有p5，其平方剩余為1和14，平方非剩余為2和3，且2和3是原根。（證）由推論1，(a)(p)p12，

6、故(a)可能為1, 2, , p1。（1）a是模p二次剩余，則由二次剩余的充分必要條件知1（mod p）由定理5.1.1知(a)，但是素?cái)?shù)，故(a)1或 而(a)1 a1（mod p），故結(jié)論成立。（2）a是模p的二次非剩余，則由二次剩余的充分必要條件知 1（mod p）即(a) ，那么，只有(a)2或p1 （(a) 也不能為1，因?yàn)橹挥?1)1，但1是平方剩余，不是非剩余）而(a)2 ap11（mod p），故結(jié)論成立。（3）由第4章結(jié)論知，p有個(gè)平方非剩余，其中只有(p1)2，其余的(a)p1，即原根有1個(gè)。（4）顯然?！纠?】取p11，驗(yàn)證推論2。（解）首先，直接計(jì)算知：1，3，4，5，

7、9是11的二次剩余，2，6，7，8，10是模11的二次非剩余。且有(1)1，(3)(4)(5)(9)5，(2)(6)(7)(8)10，(10)2【性質(zhì)1】設(shè)(a, m)1。 （1）若ba（mod m），則(b)(a)。（2）(a)。（證）（1）已知ba（mod m），所以1（mod m）所以(b)(a)。其次， 1（mod m）所以(a)(b)。 (b)(a)（2）證法一：由1（mod m）知()(a);由a1（mod m）知1（mod m），即1（mod m），從而1（mod m），所以(a)()。證法二：因?yàn)?（mod m）的充分必要條件是1（mod m）【例7】已知整數(shù)39模17的階為(

8、39)(5)16。則由此可知，整數(shù)7模17的階為16，因?yàn)?（mod 17）。 【定理5.1.2】設(shè)m1，(a, m)1，則1，a，模m兩兩不同余。特別，若a是模m的原根，則上述(m)個(gè)數(shù)構(gòu)成模m的簡(jiǎn)化剩余系。（證）反證法。若存在整數(shù)k，l（0lk(a)）使得（mod m）則由(a, m)1知1（mod m）但0kl(a)，與(a)的最小性矛盾。再設(shè)a是模m的原根，即(a)(m)，則1，a，模m兩兩不同余。由簡(jiǎn)化剩余系的等價(jià)條件知，上述(m)個(gè)數(shù)構(gòu)成模m的簡(jiǎn)化剩余系?！纠?】整數(shù) k0, 1, 2, , 15 組成模17的簡(jiǎn)化剩余系。（解）直接計(jì)算得k012345678910111213141

9、515861314210161291143157【例9】設(shè)模數(shù)m18，選整數(shù)a5和7，驗(yàn)證定理5.1.2的結(jié)論。（解）(18)6，直接計(jì)算得k012345k012315717131117131即k0,1,2,5模18兩兩不同余，k0,1,2模18兩兩不同余。且知5是模18的原根，從而k0,1,2,5組成模18的簡(jiǎn)化剩余系?！径ɡ?.1.3】設(shè)m1，(a,m)1，則 （mod m） dk（mod (a)）（證）首先(a) r， 0r(a)，q0(a) ， 0(a)，0又1（mod m），故，（mod m）必要性：已知（mod m） （mod m） 由定理5.1.2的證明過程知， r，即dk（mo

10、d (a)）（否則，設(shè)r，則有1（mod m），且r-(a)，矛盾）充分性： 若dk（mod (a)），則k(a)t （mod m）【推論】（mod m）【例10】100（mod 231），因?yàn)?2)30，10（mod 30）?！纠?1】因?yàn)?2)3，所以2（mod 7）。【定理5.1.4】（的階）設(shè)整數(shù)m1，(a,m)1，整數(shù)d0，則 ()意義：（1）用a的階求的階（2）若a為原根，可求出全部原根（3）求原根的個(gè)數(shù)（見定理5.1.5）（證）由定義5.1.1知1（mod m）由定理5.1.1，(a)d()，從而但1，故()另一方面，有 1（mod m）由定理5.1.1，()，所以 ()【例12

11、】已知(5)16， 8（mod 17），所以(8)()8(6)()16【推論】設(shè)m1，g是模m的原根，整數(shù)d0，則是模m的原根 (d,(m)1（證）由定理5.1.4，() 是原根(m) (d,(m)1【例13】由(5)16可知5是模17的原根，由原根5就可以求出17的所有原根： 5（mod 17），6（mod 17），14，（mod 17）10（mod 17），12（mod 17），11，（mod 17）13（mod 17），6（mod 17）【定理5.1.5】（原根的個(gè)數(shù)）設(shè)m1，若m有原根，則其原根個(gè)數(shù)為(m) （證）設(shè)g為原根，則由定理5.1.2知(m)個(gè)數(shù)g，是m的一個(gè)簡(jiǎn)化剩余系。而使

12、得（d，(m)）1的整數(shù)d共有(m)個(gè)，故由定理5.1.4之推論知結(jié)論成立?！纠?4】（利用某已知原根和定理5.1.5求其它原根）求出模25的所有原根。（解）首先，(25)20，(25)(20)8。故25若有原根，則其必有8個(gè)原根。計(jì)算7（mod 25），24-1（mod 25），所以2是模25的一個(gè)原根。20的簡(jiǎn)化剩余系為1, 3, 7, 9, 11, 13, 17, 19，由定理5.1.5知25的所有原根為：2，8，3，12，23，17，22，13（mod 17）即模25的原根為：2, 3, 8, 12, 13, 17, 22, 23?！就普摗吭O(shè)m1，且m有原根，設(shè)(m)，0，i1,2,k

13、則當(dāng)(a,m)1時(shí)，a是模m的原根的概率為（證）由定理5.1.5，a是模m的原根的概率為，再由歐拉函數(shù)的計(jì)算公式(m) (m)得 【定理5.1.6】設(shè)m1，(a, m)(b, m)1，若（(a)，(b)）1，則 (ab)(a)(b)反之亦然。（證）(a, m)(b, m)1，故(ab, m)1，即(ab)存在。又 1（mod m）故(a)(b)(ab)。而（(a), (b)）1，因此(a)(ab)。同理可證(b)(ab)。再利用（(a), (b)）1，得(a)(b)(ab)另一方面，1（mod m）從而 (ab)(a)(b) 即 (ab) (a)(b)反之，若(ab) (a)(b)，那么1（m

14、od m）因此， (ab)(a)，(b)即 (a)(b)(a)，(b)但 (a)(b)(a)，(b)所以 (a)(b)(a)，(b)所以 （(a)，(b)）1【例15】（利用定理5.1.6求原根）求模71的原根。（解）首先計(jì)算知2模71的階為(2)35，又知1的階為2，且(35, 2)1，故由定理5.1.6知2的階為(2)(1)(2)23570(71)所以269（mod 71）是71的原根。而(71)70，(70)24，故71有24個(gè)原根。分別為，其中i1, 3, 9, 11, 13, 17, 19, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 51, 53

15、, 57, 59, 61, 67, 69?！纠?6】（其它判斷）m19，c1025，則(10)18。那么，因?yàn)?2)18，且(5)1，故(2)(5)(10)，從而說明（(2)，(5)）1即(2)與(5)不互素。（驗(yàn)證，(5)9，故（(2)，(5)）（18，9）9）【定理5.1.7】設(shè)m，n都是大于1的整數(shù)，(a, m) (a, n) 1，那么（1）若nm，則(a)(a)（2）若(m, n) 1，則(a)(a)，(a)（證）（1）由(a)的定義知1（mod m）。而nm，故1（mod n），從而由定理5.1.1知(a)(a)（2）由（1）知(a)(a)，(a)(a)從而由最小公倍數(shù)性質(zhì)知 (a)

16、，(a)(a)。又由1（mod m）1（mod n）當(dāng)(m, n) 1時(shí)有，1（mod mn）那么，由定理5.1.1知(a)(a)，(a)【推論1】設(shè)p，q是兩個(gè)不同的奇素?cái)?shù)，(a, pq) 1，則(a)(a)，(a)【例17】設(shè)p，q是兩個(gè)不同的奇素?cái)?shù)，npq，(a, n)1，若e滿足(e,(n)1，那么存在整數(shù)d（1d(a)，使得ed1（mod (a)）且對(duì)于c（mod n），有a（mod n）（證）已知(e,(n)1且(a)(n)，故（e，(a)1。所以d（mod (a)）存在，即d1k(a)又知1（mod p），所以a（mod p）（注意為整數(shù)）即 a（mod p）同理有 a（mod

17、q）所以 a（mod n）因此 a（mod n）【推論2】設(shè)m1，(a, m) 1，且設(shè)m的標(biāo)準(zhǔn)分解式為，則(a)(a)，(a)，(a)（證）用歸納法?！纠?8】（快速求階）求(33)和(7)。 （解）已知(33, 100)1，且100。分別求(33)和(33)。(33)(1)1(33)(8)20所以(33) (33)，(33)1，2020其次(7)(3)2(7)4所以(7) (7)，(7)2，44注意 對(duì)于模m，不一定有(ab) (a)，(b)成立。例如(9)244，4(3)，(3)(21)144，4(3)，(7)但有(63)44，2(7)，(9)【定理5.1.8】設(shè)m，n都是大于1的整數(shù)，

18、(m, n)1，則對(duì)與mn互素的任意整數(shù)，存在整數(shù)a，使得(a)()，()（證）（構(gòu)造性）考慮同余方程組由中國(guó)剩余定理，方程組有唯一解xa（mod mn），則a即為所求。因?yàn)橛尚再|(zhì)1（i），有(a) (a1)，(a) (a2)從而由定理5.1.7知(a) (a)，(a) ()，()【例19】（求滿足條件的a）設(shè)m11，n27，5，14，求滿足(a)(7)，(14)的a。（解）解方程組得x95（mod 1127297），即a95驗(yàn)證：(95)90，(7)10，(14)18(7)，(14)10，1890(95)【定理5.1.9】設(shè)m1，(a, m) (b, m) 1，則存在整數(shù)c，使得(c)(a)

19、，(b)（證）（構(gòu)造性）對(duì)于整數(shù)(a)和(b)，存在整數(shù)u，v，滿足(a)，v(b)，且(u, v)1使得(a)，(b)uv令，t則 ，由定理5.1.4()u，()v，再由定理5.1.6，有()()()uv(a)，(b)故取c（mod m），即為所求。【例20】（利用定理5.1.9求原根）m3631為素?cái)?shù)，則有(3631)3630235(2)6055，(3)121025(5)3633，(6) 121025(7)33311，(10)181535(11)33023511， 12)121025(13)181535，(14)181535(15) 3630235，(17)121025由定理5.1.9，取

20、a3，b5以及u1210，v3，這時(shí)，s1，t，c2623（mod 3631）的階為(2623)(3)，(5) 1210，3633630因此，c2623是模3631的一個(gè)原根。還可利用a11，b13并選u235，v，得s11，t35，計(jì)算c338210513364（mod 3631）也為原根。原根存在的存在性與計(jì)算方法【定理5.2.1】設(shè)p為奇素?cái)?shù)，則模p的原根存在。 （證）（構(gòu)造性）記(r)，1rp1，由定理5.1.9，存在g，使 1（mod p）故e(p)p1，又e，r1, 2, , p1從而知方程 1（mod p）有p1個(gè)解 x1, 2, , p1（mod p）再由定理3.4.4， p1

21、e，即g的階為p1。（定理3.4.4：同余方程0（mod p）的解數(shù)不超過其次數(shù)（mod p）【推論】設(shè)p為奇素?cái)?shù)，d是p1的正因子，則模p階為d的元素存在。（證）利用()構(gòu)造d階元素。只要選a為原根，選(p-1)/d代入上式的d即可?！径ɡ?.2.2】設(shè)g是模p的一個(gè)原根，則g或gp是模的原根?！径ɡ?.2.3】設(shè)p為奇素?cái)?shù)，則對(duì)任意正整數(shù)，模的原根存在。進(jìn)一步，若g是模的一個(gè)原根，則對(duì)任意正整數(shù)，g是模的原根。【例】設(shè)2，p3，2是模9的一個(gè)原根，則2是模27，81，的原根。同理，2是模25的一個(gè)原根，所以2也是模125，625，的原根。【定理5.2.4】設(shè)1，g是模的一個(gè)原根，則g與g中

22、的奇數(shù)是模m2的一個(gè)原根。【例】設(shè)2，p3，2是模9的一個(gè)原根，且22，2911故11是模18的一個(gè)原根。又7是模25的一個(gè)原根，而77，72532，所以7也是50的一個(gè)原根?！径ɡ?.2.5】設(shè)a是一個(gè)奇數(shù)，則對(duì)任意3，有1（mod ）（本定理說明(a)）【定理5.2.6】設(shè)3，則(5)【定理5.2.7】模m的原根存在的充分必要條件是m2，4，2。其中p為奇素?cái)?shù)?！径ɡ?.2.8】設(shè)m1，(m)的不同素因數(shù)是，則g是模m的一個(gè)原根的充分必要條件是1（mod m），i1, 2, , k意義 ：給出了一個(gè)找原根的方法【例】求模41的所有原根。（解）(m)(41)405，2，5，20，8，故只需驗(yàn)

23、證，1？ （mod 41）驗(yàn)算：10，1（mod 41），2不是原根。1（mod 41），3不是原根。18，1（mod 41），5不是原根。10，401（mod 41），6是原根。再由定理5.1.4和5.1.5，(41)40的簡(jiǎn)化剩余系為1，3，7，9，11，13，17，19，21，23，27，29，31，33，37，39共有(41)(40)16個(gè)數(shù)，那么原根為6，11，7（mod 41）【例】設(shè)模數(shù)m1681，求模m的原根。（解）已知6是模41的原根，故由定理5.2.2知，6或64147是模1681的原根。計(jì)算1431413（mod ），151814137（mod ）即1（mod ），1（m

24、od ）所以6和47都是模1681的原根（因()16404140）。另由定理5.2.3，6和47是所有模的原根。【例】設(shè)模數(shù)m23362，求模m的原根。（解）由例2知6和47是模的原根，故由定理5.2.4知，61687和47是模23362的原根?！径ɡ?.2.9】設(shè)p為素?cái)?shù)，正整數(shù)d(p)p1，則對(duì)模數(shù)p而言，階為d的數(shù)恰有個(gè)(d)。（證）見定理5.2.1的第二種證明過程。例p13，(p)12223，其因數(shù)有d1, 2, 3, 4, 6, 12故對(duì)模數(shù)13而言：1階元素有(1)1個(gè)，即a1；2階元素有(2)1個(gè)，即a12-1；3階元素有(3)2個(gè)，即a3, 9；4階元素有(4)2個(gè)，即a5,

25、8；6階元素有(6)2個(gè)，即a4, 10；12階元素有(12)4個(gè)，即a2, 6, 7, 11。【定理5.2.10】設(shè)為奇素?cái)?shù)，若，則，1, 2, ,都不是的原根。（證）由定理6.1.5，對(duì)模的階為算法：S1：列出備選整數(shù)表：1, 2, 3, , S2：選小的正整數(shù)，求對(duì)的階。S3：若，則不是原根，那么就在備選整數(shù)表中除去以下各數(shù)：S4：若備選整數(shù)表只剩下個(gè)數(shù)，則輸出表中全部整數(shù)（即全部原根）；否則，轉(zhuǎn)S2說明：（1）在S3步，若，則是的原根，即可結(jié)束上述過程，利用定理6.1.5的推論獲得全部原根。（2）由于奇素?cái)?shù)有個(gè)原根，故最后剩下的個(gè)數(shù)肯定是的原根?！纠坷枚ɡ?.2.9給出的方法求模4

26、1的所有原根。（解）40，由定理6.1.1的推論，的階的可能值只有1, 2, 4, 5, 8, 10, 20, 40。16，即23有16個(gè)原根。模數(shù)23的備選整數(shù)表為：1, 2, 3, , 40選2，計(jì)算10（mod 41），401（mod 41），所以即2040，故2不是41的原根。在備用表中除去（1, 2, , 20）：2, 4, 8, 16, 32, 23, 5, 10, 20, 40, 39, 37, 33, 25, 9, 18, 36, 31, 21, 1表中剩余整數(shù)為3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 2

27、9, 30, 34, 35, 38再選3，計(jì)算401（mod 41），所以8，3不是原根。在備用表中除去（1, 2, , 8）： 3, 9, 27, 40, 38, 32, 14, 1其中1, 9, 32, 40共4個(gè)數(shù)在第一次已被剔除。此時(shí)表中剩下16個(gè)數(shù)：6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35顯然都是原根。對(duì)數(shù)及n次剩余目的：研究以下同余方程有解的條件和解數(shù)：a（mod m），(a, m)1背景問題：設(shè)g是模m的一個(gè)原根，則當(dāng)x遍歷模(m)的最小正完全剩余系時(shí)，遍歷模m的一個(gè)簡(jiǎn)化剩余系。故對(duì)任意y，(y, m

28、)1，則存在唯一的整數(shù)x（1x(m)），使得y（mod m）【例1】：m10，(10)4，其簡(jiǎn)化剩余系為1，3，7，9。又知(1)1，(3)4，(7)4，(9)2。即3和7是模10的原根。選g3，則1, 2, 3, 4, 5, 6, 7, 8, 9, 10時(shí)有3，9，7，1（mod m）是10的簡(jiǎn)化剩余系。故x只需遍歷1, 2, 3, 4(10)即可?！纠?】：m18，(18)6，18的簡(jiǎn)化剩余系為1, 5, 7, 11, 13, 17。由(6)2知，模18有兩個(gè)原根5和11。選g5，則1, 2, 3, 4, 5, 6, 7, , 185，7，17，13，11，1（mod m）是18的簡(jiǎn)化剩余

29、系。故x只需遍歷1, 2, 3, 4, 5, 6(18)即可。定義【定義5.3.1】設(shè)g是模m的一個(gè)原根，對(duì)已知的a，存在整數(shù)r，使得式a（mod m） （1）成立，則稱r為以g為底的a對(duì)模m的一個(gè)離散對(duì)數(shù)（簡(jiǎn)稱為對(duì)數(shù)），記作r或，。對(duì)數(shù)也稱為指標(biāo)，記為r或?！纠浚ɡ弥笖?shù)函數(shù)和窮舉求離散對(duì)數(shù)）已知5是模17的原根。求5對(duì)17的離散對(duì)數(shù)。（解）先構(gòu)造以5為底的指數(shù)函數(shù)表12345678910111213141516a58613142101612911431571再由上表構(gòu)造離散對(duì)數(shù)表12345678910111213141516r16613121315210711945148離散對(duì)數(shù)的性質(zhì)【

30、定理5.3.1】設(shè)m1，g是模m的一個(gè)原根，(a, m)1，若整數(shù)r使得a（mod m）成立，則r滿足r（mod (m)）（證）因?yàn)?a, m)1，故a（mod m）從而 1（mod m）又知g模m的階為(m)，由定理5.1.1知(m)r故 r（mod (m)）【例】已知5是17的一個(gè)原根，且r38，那么，計(jì)算可得2（mod 17）而6，故386（mod (17)=16）（說明，a的對(duì)數(shù)的值實(shí)質(zhì)上有無窮多，如對(duì)模數(shù)17及其原根5而言， 由6（mod (17)16）知，2的對(duì)數(shù)有6，22，38，54，）（也可以說有同一真數(shù)的對(duì)數(shù)有無窮多）（原因： 2（mod 17）（本質(zhì)：1（mod 17）【推

31、論】設(shè)m1，g是模m的一個(gè)原根，(a, m)1，則10（mod (m)），g1（mod (m)）（證）因?yàn)?（mod m），g（mod m）【定理5.3.2】設(shè)m1，g是模m的一個(gè)原根，若(, m)1（1,2,n），則（mod (m)）特別地n（mod (m)）（證）令（i1,2,n），由對(duì)數(shù)的定義5.3.1（mod m）， i1, 2, , n從而 （mod m）由定理5.3.1， ()r1+r2+rn（mod (m)）即結(jié)論成立。【定理5.3.3】設(shè)m1，g是模m的一個(gè)原根，整數(shù)r滿足1r(m)，則以g為底的對(duì)模m有相同對(duì)數(shù)r的所有整數(shù)全體是模m的一個(gè)簡(jiǎn)化剩余類。（證）因r，(, m)1由

32、對(duì)數(shù)的定義5.3.1，ara（mod m）故以g為底的對(duì)模m有同一對(duì)數(shù)r的所有整數(shù)都屬于所在的模m的一個(gè)簡(jiǎn)化剩余類。（說明，對(duì)數(shù)r的真數(shù)a的值實(shí)質(zhì)上有無窮多，如對(duì)模數(shù)17及其原根5而言， 由2（mod 17）知，對(duì)數(shù)6對(duì)應(yīng)的真數(shù)有2，19，36，53，）（也可以說有同一對(duì)數(shù)的真數(shù)也有無窮多）【例】作模41的對(duì)數(shù)表。（解）已知6是模41的原根，計(jì)算(mod 41)得以6為底的離散對(duì)數(shù)表y（行標(biāo)為x的十位數(shù)，列表為x的個(gè)位數(shù)，交叉位置為對(duì)數(shù)y）012345678904026151222139383018327312537243316923414293613417511732328101819212

33、32356420由此可構(gòu)造反對(duì)數(shù)表（即指數(shù)函數(shù)表，y）：01234567890619112527392910191322842421318263334240355301614212312239133717203823158741【例】設(shè)模數(shù)m41，分別求整數(shù)a29，18以6為底的離散對(duì)數(shù)。（解）查上例所給離散對(duì)數(shù)表，可得(28)11，(18)16計(jì)算離散對(duì)數(shù)的復(fù)雜度：求離散對(duì)數(shù)是困難問題。即已知模數(shù)m及其一個(gè)原根g，當(dāng)已知某個(gè)整數(shù)x的指數(shù)函數(shù)值y（mod m）時(shí)，求xy，是NP問題。離散對(duì)數(shù)的計(jì)算Pohlid-Hellman法Pohlid-Hellman（波里德-海爾曼）算法主要是利用原根的性

34、質(zhì)以及的分解結(jié)果，實(shí)現(xiàn)離散對(duì)數(shù)的計(jì)算。其中為素?cái)?shù)。設(shè)和都是正整數(shù)，為素?cái)?shù)，是的原根。求正整數(shù)x，滿足設(shè)有標(biāo)準(zhǔn)分解式， ，那么，根據(jù)中國(guó)剩余定理，只要能確定， 則便能求得。即由中國(guó)剩余定理可得其中，且（i1, 2, , ）。下面討論求的方法，其中以為例：由于，故由于，故有，從而有由于是原根，即，故而另一方面（j2, 3, , ），故j1時(shí)，有所以將表示為進(jìn)制，即記，j0, 1, , 那么即那么，比較等式兩邊就可以確定。但由于等式左邊是已知的，而右邊的是未知的，故確定的方法是：令0, 1, , ，分別計(jì)算，那么，必存在某個(gè)（），使得上式成立，即，從而可知。如果，1，則可以確定，即。若2，則需進(jìn)一步

35、確定等。而一旦確定了，就可以利用它繼續(xù)確定。因?yàn)楣嗜袅?，就有?那么，類似于確定的方法，由上式可以確定。同理，若3，可令，則有由上式可以確定。以此類推，可得。另外，由上邊的推導(dǎo)過程可以看出，在確定時(shí)，每次都要反復(fù)用到（0, 1, , ），故為了計(jì)算方便，可以令，預(yù)先計(jì)算好（顯然1（mod ），并列表以備使用時(shí)直接查表即可?！纠?.4.1】設(shè)8101，6，y7833。求x使之滿足（解）首先有81016135016(1350)1（mod 8101） 13506751（mod 8101）其次，分解得8100對(duì)2，有8100（mod 8101），并構(gòu)造表（見表6.4.1）。表6.4.1 18100對(duì)3

36、，有5883（mod 8101），2217（mod 8101），構(gòu)造表（見表6.4.2）。表6.4.2 158832217對(duì)5，有3547（mod 8101），構(gòu)造表（見表6.4.3）。表6.4.3 1354735670775221（a）2，2：需要分別確定以獲得。（a.1）計(jì)算8100（mod 8101）查表6.4.1知8100。所以1（a.2）計(jì)算783367515356（mod 8101）1（mod 8101）查表6.4.1知1。所以0 1021（b）3，4：需要分別確定以獲得。（b.1）計(jì)算2217（mod 8101）查表6.4.2知2217。所以2（b.2）計(jì)算3593（mod 81

37、01）2217（mod 8101）查表6.4.2知2217。所以2（b.3）再算3708（mod 8101）5883（mod 8101） 1（b.4）再算6926（mod 8101）5883（mod 8101） 1 2231144（c）5，2356（mod 8101） 23593（mod 8101）356（mod 8101） 2 22512最后，計(jì)算2025，100，324并分別解同余方程得，。 11202544100641232424（mod 8100）4337（mod 8100） 7833（mod 8101）或4337（mod 8100）最后需要說明的是：由前面的推導(dǎo)過程可以看出，Pohl

38、id-Hellman算法是利用窮舉和比較求得，并由其再求得，最終得到問題的答案。故當(dāng)只有小的素因數(shù)時(shí)，此算法有效。反之，只要有一個(gè)很大的素因數(shù)，則使用本算法的意義并不大。因?yàn)榇藭r(shí)計(jì)算（0, 1, , ）的工作量還是很大的。Shank法Shank（商克）法是一種比較有效的算法，不僅速度快，而且需要的存儲(chǔ)量也較少。設(shè)已知素?cái)?shù)p、整數(shù)a和y，求x滿足， 0 xn其中n是a的乘法周期，即。問題等價(jià)于求離散對(duì)數(shù)。Shank法的運(yùn)算是在有限域上進(jìn)行（即是在集合0, 1, 2, ,1上關(guān)于模素?cái)?shù)的加法和乘法運(yùn)算，有限域概念見9.4）。其基本思想是：選一整數(shù)，設(shè)，0rd，故只要求得和r，就等于求出了x。令0,

39、 1, ,，計(jì)算，并構(gòu)造一個(gè)指數(shù)函數(shù)表。為了便于檢索，按值的增序排列。由于假定，所以令0, 1, 2, ，逐個(gè)計(jì)算，直到等于表中某個(gè)（）為止。那么，必有，輸出。Shank法可以歸納如下，其中已知素?cái)?shù)、底數(shù)a、真數(shù)y和a的乘法周期，且所有運(yùn)算都在上進(jìn)行：S1. 選擇；0；1S2. 將的值填入指數(shù)函數(shù)表S3. 若r，則 對(duì)表格數(shù)據(jù)按的值增序排列；轉(zhuǎn)S4 否則 ；轉(zhuǎn)S2 /完成建表S4. 計(jì)算：；0 /賦初值S5. 若表中存在一對(duì)數(shù)，滿足，則令；輸出；算法結(jié)束否則；轉(zhuǎn)S5 /迭代求解【例6.4.2】在GF（23）上求。（解）5的乘法周期為22，故5是23的原根。對(duì)于很小的23，可以窮舉求解，即計(jì)算：

40、1，5，2，19，3。所以?，F(xiàn)在用Shank法求解：選，針對(duì)0, 1, , d1即0, 1, 2, 3, 4計(jì)算，建立指數(shù)函數(shù)表（見表6.4.4），其中按的增序排列。表6.4.4 (mod 23)的指數(shù)函數(shù)表12451002413計(jì)算，3，0檢查：因表中無3，故繼續(xù)計(jì)算：15322，1（即計(jì)算的是22）檢查：表中無22，繼續(xù)計(jì)算：15228，2（即計(jì)算8）檢查：表中無8，繼續(xù)計(jì)算：1585，3（即5）檢查：表中存在5，對(duì)應(yīng)的1，故有35116 或 另外，若的乘法周期可以分解，則該方法還可化簡(jiǎn)。思路如下：設(shè)（），則的乘法周期為，的乘法周期為。若 （0）則 ，0，0令 由于 即 令 則 由此得時(shí)，

41、求的算法如下：S1. ；S2. 求S3. ；S4 . 求S5. 輸出 二項(xiàng)同余方程n次剩余二項(xiàng)同余方程：a（mod m）， 1【定義5.5.1】設(shè)m1，(a, m)1，若n次同余方程a（mod m） （1）有解，則a叫做對(duì)模m的n次剩余；否則，叫做對(duì)模m的n次非剩余?！纠壳?次同余方程9（mod 41）的解。（解）查模數(shù)為41，底數(shù)為6的離散對(duì)數(shù)表，可得(9)30，即9（mod 41）。再令 （mod 41）原方程變?yōu)?（mod 41）因6是原根，故由定理5.3.15y30（mod 40(41)） （2）（5, 40）5，且530，故此方程有5個(gè)解）即 y6（mod 8）故（2）的解為 y6

42、，14，22，30，38（mod 40） ，39，21，5，9，8（mod 41）故9是模41的5次剩余?！纠壳?次同余方程9（mod 41）的解。（解）因?yàn)?9)30，即9（mod 41）。再令 （mod 41）原方程變?yōu)?（mod 41）6是原根，故有 7y30（mod 40(41)）解之，得 y10（mod 40）故原方程有唯一解 x32（mod 41）【例】求8次同余方程9（mod 41）的解。（解）因?yàn)?9)30，即9（mod 41）。再令 （mod 41）原方程變?yōu)?（mod 41）6是原根，故有 8y30（mod 40(41)）此方程無解，故原方程無解?！径ɡ?.5.1】設(shè)m1

43、，g是模m的一個(gè)原根，(a, m)1，則同余方程a（mod m） （3）有解。且在有解的情況下，解數(shù)為。（證）若方程（3）有解（mod m）則分別存在非負(fù)整數(shù)u, r，使得（mod m），a（mod m）由（3）得（mod m）由定理5.3.1知 nur（mod (m)）（可以理解為將方程gnugr（mod m）兩邊同時(shí)以g為底取對(duì)數(shù)，但要注意取對(duì)數(shù)后模數(shù)變?yōu)?m)）即方程 nyr（mod (m)） （4）有解（且解為yu（mod (m)），故（n,(m)）ra反之，若，則方程（4）有解yu（mod (m)）且解數(shù)為d(n,(m)。因此，方程（3）有解（mod m）且解數(shù)也為d(n,(m)【推

44、論】在定理5.5.1條件下，a是模m的n次剩余的充分必要條件是1（mod m），其中d(n，(m)。（定理5.5.1：設(shè)m1，g是模m的一個(gè)原根，(a, m)1，則同余方程a（mod m）有解（n,(m)）a。且在有解的情況下，解數(shù)為（n,(m)）（證）設(shè)a（mod m），若a是模m的n次剩余，即方程a（mod m）有解，再由定理5.5.1知，即dr，所以1（mod m）反之，由1（mod m）知1（mod m）。而g是原根，即g的階數(shù)為(m)，故由定理5.1.1(m)即?！纠拷馔喾匠?3（mod 41）。（解）d(n，(m)(8，(41)(8，40)8。查表得 (23)36因?yàn)?36，故

45、原方程無解?！纠拷馔喾匠?7（mod 41）。（解）d(n，(m)(12，(41) )(12，40)4。查表得 (37)32因?yàn)?32，故方程有4個(gè)解。求等價(jià)方程，原方程兩邊同時(shí)取對(duì)數(shù)，得12x37（mod 40）即12x32（mod 40） （5）（即方程12y32（mod 40），對(duì)應(yīng)方程（4）：nyr（mod (m)），此處n12，r32）利用同余性質(zhì)有3x8（mod 10）解為x6（mod 10）方程（5）的解為x6，16，26，36（mod 40）查離散對(duì)數(shù)的反函數(shù)表（即指數(shù)函數(shù)表）得原方程的解為，39，18，2，23【定理5.5.2】設(shè)m1，g是模m的一個(gè)原根，(a, m)1，

46、則a對(duì)m的階數(shù)為(a)特別地，a是模m的原根的充分必要條件為(a, (m)1。（證）由定理5.1.4即得。（定理5.1.4：設(shè)整數(shù)m1，(a, m)1，整數(shù)d0，則()）（此處的g即定理中的a，a即定理中的ad，而g是原根（即g的階數(shù)為(m)），故必存在整數(shù)r（1r(m)），使得agr（mod m），此處的r即定理中的d，且有ra）【定理5.5.3】設(shè)m1，g是模m的一個(gè)原根，則模m的簡(jiǎn)化剩余系中，階是e的整數(shù)共有(e)個(gè)。特別地，原根共有(m)個(gè)。（證）因m有原根g，由定理5.1.3，知a的階為(a)()顯然，a的階是e的充分必要條件是e，即(m), d)令d（0e）。則上式等價(jià)于（, e）

47、1（否則（, e）1，設(shè)（, e）k，則d。而顯然有(m)，故(m), d)，矛盾）。而滿足（, e）1的顯然有(e)個(gè)，故階為(m)的整數(shù)個(gè)數(shù)是(m)，即原根個(gè)數(shù)為(m)。原根與離散對(duì)數(shù)的應(yīng)用DiffieHellman密鑰交換算法原根的應(yīng)用ElGamal加密算法構(gòu)造全局變量 既可以用于加密，也可以用于簽名，其安全性依賴于有限域上計(jì)算離散對(duì)數(shù)的難度 要產(chǎn)生一對(duì)密鑰，首先選擇一素?cái)?shù)p，整數(shù)模p的一個(gè)原根g，隨機(jī)選取x，g和x都小于p，然后計(jì)算：y（mod p） 公開密鑰是y，g，p，其中g(shù)，p可以為一組用戶共享 私有密鑰是xElGamal加密算法 將明文信息M表示成 0, 1, , p1 范圍內(nèi)

48、的數(shù) 加密: 秘密選擇隨機(jī)數(shù)k， 計(jì)算： a（mod p） bM（mod p） 密文為(a, b) 解密:M（mod p）其中除法表示乘法b（原理：因（mod p），故M（mod p）（不足：信息有擴(kuò)張）例 生成密鑰：使用者A選取素?cái)?shù)p2357及的生成元g2，A選取私鑰x1751并計(jì)算公鑰y（mod p）（mod 2357）1185A的公鑰是p2357， g2， y1185 加密：為加密消息M2035， 消息的發(fā)送方B選取一個(gè)隨機(jī)整數(shù)k1520 并計(jì)算a（mod p）215201430（mod 2357）bM（mod p）2035697（mod 2357） （其中（mod p）2084（mod

49、 2357）B發(fā)送（a, b）（1430, 697）給A 解密：A計(jì)算 872 (mod 2357)Mb697872 2035 (mod 2357)ElGamal加密算法安全性 復(fù)雜度：攻擊ElGamal加密算法等價(jià)于解離散對(duì)數(shù)問題 要使用不同的隨機(jī)數(shù)k來加密不同的信息 假設(shè)用同一個(gè)k來加密兩個(gè)消息，所得到的密文分別為和，則b1/b2M1/M2，故當(dāng)已知時(shí)，可以很容易地計(jì)算出來。即b1/b2同理b2/b1 例如，已知p2357，g2，x1751，y1185（mod 2357）選 k1520，則消息2035的密文為(a1,b1)(1430，697)還選 k1520，消息100的密文為(a2,b2

50、)(1430，984)消息1000的密文為(a3,b3)(1430，412)那么，設(shè)已知2035，則有b2/b120359846971100（mod 2357）b3/b1203541269711000（mod 2357）（其中6971700（mod 2357）改進(jìn)的隨機(jī)數(shù)生成算法利用同余運(yùn)算生成偽隨機(jī)數(shù)的Lehmer算法（也稱線性同余法（LCGS）：， 1, 2, 同時(shí)討論了其安全性。該算法的循環(huán)周期嚴(yán)重依賴于乘數(shù)、增量和種子值的選擇。其實(shí)質(zhì)在于（mod ）即每個(gè)完全由m、a、c及決定。故算法關(guān)鍵是如何確定參數(shù)m、a、c和?！径ɡ?.6.1】（Hull和Dobell）由Lehmer算法生成的隨

51、機(jī)數(shù)列為滿周期數(shù)列的充分必要條件是（）1；（）若存在素?cái)?shù)，使得，則必有；（）若，則必有。（證）（略）。條件（）意味著c和m互素。條件（）是指1即若，則可得其中q為m的素因數(shù)。由條件（），若為整數(shù)，可設(shè)獲得滿周期或足夠長(zhǎng)的周期是對(duì)所有隨機(jī)數(shù)生成算法的重要考量指標(biāo)之一。其中較常見的有混合線性同余法（Mixed LCGS，選0）和乘法線性同余法（Multi plicative LCGS，c0）。（1）混合線性同余法對(duì)于0，有可能使得周期T=m。此處僅討論如何選擇m。為得到盡可能大的周期，以及在（0, 1）區(qū)間內(nèi)的高密度的隨機(jī)數(shù)，故希望m盡可能大。其次，利用除以而獲得余數(shù)，是一項(xiàng)十分緩慢的算法操作。故

52、為了避免這種除法操作，較好的選擇是，其中b為計(jì)算機(jī)用于存放實(shí)際數(shù)值的字長(zhǎng)，這樣就就能夠利用整數(shù)溢出來避免這種明顯的除以m的操作?？晒┻x用的混合線性同余法有（）；（）。（2）乘法線性同余法本方法的優(yōu)點(diǎn)在于不需要（0）。由于條件（）不能滿足，因而不能達(dá)到滿周期。但仍可以適當(dāng)選擇與，使。此方法是比較有效的方法，也是線性同余法中被采用得較多的方法。Hutchinson建議取小于的最大素?cái)?shù)。那么，對(duì)于素?cái)?shù)而言，可以證明，如果是以為模的素因數(shù)，則周期。顯然，這只要選為的原根，且1即可，這時(shí)在每一個(gè)循環(huán)里，嚴(yán)格地獲得每個(gè)整數(shù)1, 2, , 各一次，而且選為從1至之間的任意整數(shù)，都能保證。這種方法稱為素?cái)?shù)模乘

53、法線性同余法（PMMLCGs）。對(duì)于方法PMMLCGs，由于不能選為模，因而不能運(yùn)用溢出的機(jī)理去影響除法的模。針對(duì)此情況，Payne、Rabung和Bogyo等人提出了一種避免明顯除法，運(yùn)用溢出原理的方法模擬除法。由 知 ，令 若 ，則 若 ，則令數(shù)列提供了時(shí)的隨機(jī)序列，并且遵從原則式中可由移模減數(shù)而得。PMMLCGs的實(shí)際用例：35，小于的最大素?cái)?shù)為，且時(shí)3125，生成的隨機(jī)數(shù)具有較好的特性；對(duì)于35，小于的最大素?cái)?shù)為，且兩種得到廣泛應(yīng)用的關(guān)于的選擇為：16807和。（3）Fibonacci法此方法是建立在Fibonacci（斐波那契）數(shù)列的基礎(chǔ)上，其遞歸公式為， 1, 2, Fibonac

54、ci法需要兩個(gè)初值和。其得到的周期有可能大于，但它所生成的序列的隨機(jī)性較差，故不能提供滿意的結(jié)果。（4）二次同余法由Coveyon提出的二次同余法近似相當(dāng)于雙精度的中間平方法，但卻比后者有較長(zhǎng)的周期。其遞歸公式為， 1, 2, 一種快速傅里葉變換算法【定義6.6.1】離散傅里葉變換（DFT）：Fourier變換矩陣，另法表示：運(yùn)算量：次復(fù)數(shù)乘法和次復(fù)數(shù)加法【定義6.6.2】設(shè)和是兩個(gè)周期為的序列，其互相關(guān)函數(shù)定義為，0, 1, 2, , 【定理6.6.2】設(shè)是一個(gè)奇素?cái)?shù)，則式（5.6.1）可化為兩個(gè)周期為的序列的互相關(guān)函數(shù)，和次加法來計(jì)算。（證）設(shè)，1, 2, , （5.6.2）則有，1, 2

55、, , （5.6.3）又設(shè)是的一個(gè)原根，則1, 2, , 可表為（0, 1, , ），即除以的最小非負(fù)余數(shù)，于是式（5.6.2）化為，0, 1, , （5.6.4）由于是原根，所以式（5.6.4）是兩個(gè)周期為的序列（0, 1, ）和（0, 1, ）的互相關(guān)函數(shù)，再由式（5.6.3）的次加法給出全部。同理，對(duì)于和2（是一個(gè)奇素?cái)?shù)），也有類似的結(jié)果。同余方程的求解【例6.6.3】解同余方程169（mod 41）。（解）此處利用離散對(duì)數(shù)求解。已知6是41的原根，故對(duì)方程兩邊取以6為底的對(duì)數(shù)，有再由定理6.3.2，方程可表為查離散對(duì)數(shù)函數(shù)表6.3.4有，代入上式得24 再查指數(shù)函數(shù)表6.3.3得39（

56、mod 41）。所以原方程的解為39（mod 41）利用離散對(duì)數(shù)還可以解冪同余方程，1 （6.6.5）其中m有原根g。【定理6.6.3】設(shè)整數(shù)m1，其原根為g。那么，冪同余方程（6.6.5）有解的充分必要條件是 （6.6.6）記，如果方程有解，則其解數(shù)為其通解為，（證）由于m有原根g，故等式（6.6.5）兩邊針對(duì)模數(shù)m取以g為底的對(duì)數(shù)，有 （6.6.7）顯然冪同余方程（6.6.5）與一次同余方程（6.6.7）同時(shí)有解或無解，且解數(shù)也相同。而方程（6.6.7）為一次同余方程，故由定理4.4.2可推導(dǎo)出本定理的所有結(jié)論?！纠?.6.4】判斷冪同余方程2（mod 17）是否有解，若有解，請(qǐng)求其解。（

57、解）16，查表6.3.2知7，6，（16, 7）1，顯然方程有解。由例6.1.4知5是17的一個(gè)原根，對(duì)方程兩邊取以5為底的對(duì)數(shù)即7x6（mod 16）解之得，即為原方程的解?！纠?.6.5】判斷冪同余方程16（mod 17）是否有解，若有解，請(qǐng)求其解。（解）查表6.3.2得12，8，（16, 12）4，且，所以方程有解。對(duì)方程兩邊取以5為底的對(duì)數(shù)得一次同余方程12x8（mod 16）解之得2, 6, 10, 14（mod 16），即為原方程的解。比較例6.6.4和例6.6.5，一個(gè)為單解，一個(gè)為多解，其本質(zhì)原因在于指數(shù)函數(shù)的底數(shù)10是17的原根，故對(duì)應(yīng)真數(shù)2，使得2（mod 17）成立的模16不同余的x只能有一個(gè)，而后者中函數(shù)的底數(shù)4不是原根，其對(duì)模數(shù)17的階為4，故對(duì)模數(shù)4來說，其解為1；而對(duì)模數(shù)16來說，其不同余的解則為4個(gè)。單向函數(shù)單向函數(shù)（1）給定x，計(jì)算yf(x)是容易的；（2）給定y， 計(jì)算x是不可行的。例如：對(duì)給定的g，已知x，計(jì)