《数论算法》教案-5章(原根与离散对数)

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业原根与离散对数内容整数的阶原根有原根的整数离散对数（指标）要点原根及其意义有原根的整数的条件离散对数及其性质阶及其基本性质准备知识：欧拉定理：m1，(a, m)1，则1（mod m）问题：是否是使得上式成立的最小正整数？该最小正整数有何性质？阶和原根概念【定义5.1.1】设m1，(a, m)1，则使得1（mod m）成立的最小正整数e叫做a对模m的阶（或指数），记作(a)。若a的阶e，则a叫做模m的原根。应用：DiffieHellman密钥交换算法公钥算法的核心：仅依赖

2、公开信息不足以对算法构成威胁；掌握私钥者可轻易获得信内容。全局公开量q 素数 q的原根（q）生成用户密钥用户A选择秘密的 q计算公开的 （mod q）用户B选择秘密的 q计算公开的 （mod q）交换公开密钥AB： BA： 生成公共密钥K用户A计算 K（mod q）用户B计算 K（mod q）说明：K（mod q）例：素数q353，原根3A选97， 计算40 mod 353B选233， 计算248 mod 353A与B交换A计算密钥 K160 mod 353B计算密钥 K160 mod 353用定义求阶和原根【例1】（按定义求阶和原根）m7，则(7)6。且1，1，1，1，1，1（mod 7）故

3、对模数7而言，1，2，3，4，5，6的阶分别为1，3，6，3，6，2。列表表示为a123456(a)136362因此，3，5是模7的原根。【例2】（快速求阶）m1427， (14)6，则1，1，1，1，1，1（mod 7）列表a13591113(a)166332故3，5是模14的原根。【例3】（无原根的整数）m1535， (15)8，则a12478111314(a)14244242故模数15没有原根。同理，可知模数m9时，其原根为2，5；而整数8则没有原根。也可以计算验证5是模3、6、9、18的原根。阶的性质【定理5.1.1】设m1，(a, m)1，d为正整数，则1（mod m） (a) d即

4、d0（mod (a)）（证）充分性：设(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)只需计算，其中i(m)。【例4】（用定理5.1.1结论快速求阶及原根）（例7）求(5)的值。（解）(17)16，只需计算（mod 17），其中d1，2，4，8，16（实际上不必计算）。5，8，134，161（mod 17）所以，(5)16，即5是模17的原根。【例5】求(4)、(5)、(7)的值。（解）(33)20。只需计算、（

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】设p是奇素数，也是奇素数，pa，则（1）若a是模p的二次剩余，则a不是p的原根，且当a1（mod p）时，(a)1；当a1（mod p）时，(a)；（2）若a是模p二次非剩余，则当ap1（mod p）时，(a)2；当ap1（mod p）时，(a)p1。（3）此时，p有1个原根。（4）当2为偶素数时，必有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)，但是素数，故(a)1或 而(a)1 a1（mod p），故结论成立。（2）a是模p的二次非剩余，则由二次剩余的充分必要条件知 1（mod p）即(a) ，那么，只有(a)2或p1 （(a) 也不能为1，因为只有(1)1，但1是平方剩余，不是非剩余）而(a)2 ap11（mod p），故结论成立。（3）由第4章结论知，p有个平方非剩余，其中只有(p1)2，其余的(a)p1，即原根有1个。（4）显然。【例6】取p11，验证推论2。（解）首先，直接计算知：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【性质1】设(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)()。证法二：因为1（mod m）的充分必要条件是1（mod m）【例7】已知整数39模17的阶为(

8、39)(5)16。则由此可知，整数7模17的阶为16，因为5（mod 17）。 【定理5.1.2】设m1，(a, m)1，则1，a，模m两两不同余。特别，若a是模m的原根，则上述(m)个数构成模m的简化剩余系。（证）反证法。若存在整数k，l（0lk(a)）使得（mod m）则由(a, m)1知1（mod m）但0kl(a)，与(a)的最小性矛盾。再设a是模m的原根，即(a)(m)，则1，a，模m两两不同余。由简化剩余系的等价条件知，上述(m)个数构成模m的简化剩余系。【例8】整数 k0, 1, 2, , 15 组成模17的简化剩余系。（解）直接计算得k012345678910111213141

9、515861314210161291143157【例9】设模数m18，选整数a5和7，验证定理5.1.2的结论。（解）(18)6，直接计算得k012345k012315717131117131即k0,1,2,5模18两两不同余，k0,1,2模18两两不同余。且知5是模18的原根，从而k0,1,2,5组成模18的简化剩余系。【定理5.1.3】设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)）（否则，设r，则有1（mod m），且r-(a)，矛盾）充分性： 若dk（mod (a)），则k(a)t （mod m）【推论】（mod m）【例10】100（mod 231），因为(2)30，10（mod 30）。【例11】因为(2)3，所以2（mod 7）。【定理5.1.4】（的阶）设整数m1，(a,m)1，整数d0，则 ()意义：（1）用a的阶求的阶（2）若a为原根，可求出全部原根（3）求原根的个数（见定理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【推论】设m1，g是模m的原根，整数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】（原根的个数）设m1，若m有原根，则其原根个数为(m) （证）设g为原根，则由定理5.1.2知(m)个数g，是m的一个简化剩余系。而使

12、得（d，(m)）1的整数d共有(m)个，故由定理5.1.4之推论知结论成立。【例14】（利用某已知原根和定理5.1.5求其它原根）求出模25的所有原根。（解）首先，(25)20，(25)(20)8。故25若有原根，则其必有8个原根。计算7（mod 25），24-1（mod 25），所以2是模25的一个原根。20的简化剩余系为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。【推论】设m1，且m有原根，设(m)，0，i1,2,k

13、则当(a,m)1时，a是模m的原根的概率为（证）由定理5.1.5，a是模m的原根的概率为，再由欧拉函数的计算公式(m) (m)得 【定理5.1.6】设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的原根。（解）首先计算知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个原根。分别为，其中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。【例16】（其它判断）m19，c1025，则(10)18。那么，因为(2)18，且(5)1，故(2)(5)(10)，从而说明（(2)，(5)）1即(2)与(5)不互素。（验证，(5)9，故（(2)，(5)）（18，9）9）【定理5.1.7】设m，n都是大于1的整数，(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)从而由最小公倍数性质知 (a)

16、，(a)(a)。又由1（mod m）1（mod n）当(m, n) 1时有，1（mod mn）那么，由定理5.1.1知(a)(a)，(a)【推论1】设p，q是两个不同的奇素数，(a, pq) 1，则(a)(a)，(a)【例17】设p，q是两个不同的奇素数，npq，(a, n)1，若e满足(e,(n)1，那么存在整数d（1d(a)，使得ed1（mod (a)）且对于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）（注意为整数）即 a（mod p）同理有 a（mod

17、q）所以 a（mod n）因此 a（mod n）【推论2】设m1，(a, m) 1，且设m的标准分解式为，则(a)(a)，(a)，(a)（证）用归纳法。【例18】（快速求阶）求(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注意 对于模m，不一定有(ab) (a)，(b)成立。例如(9)244，4(3)，(3)(21)144，4(3)，(7)但有(63)44，2(7)，(9)【定理5.1.8】设m，n都是大于1的整数，

18、(m, n)1，则对与mn互素的任意整数，存在整数a，使得(a)()，()（证）（构造性）考虑同余方程组由中国剩余定理，方程组有唯一解xa（mod mn），则a即为所求。因为由性质1（i），有(a) (a1)，(a) (a2)从而由定理5.1.7知(a) (a)，(a) ()，()【例19】（求满足条件的a）设m11，n27，5，14，求满足(a)(7)，(14)的a。（解）解方程组得x95（mod 1127297），即a95验证：(95)90，(7)10，(14)18(7)，(14)10，1890(95)【定理5.1.9】设m1，(a, m) (b, m) 1，则存在整数c，使得(c)(a)

19、，(b)（证）（构造性）对于整数(a)和(b)，存在整数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为素数，则有(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，这时，s1，t，c2623（mod 3631）的阶为(2623)(3)，(5) 1210，3633630因此，c2623是模3631的一个原根。还可利用a11，b13并选u235，v，得s11，t35，计算c338210513364（mod 3631）也为原根。原根存在的存在性与计算方法【定理5.2.1】设p为奇素数，则模p的原根存在。 （证）（构造性）记(r)，1rp1，由定理5.1.9，存在g，使 1（mod p）故e(p)p1，又e，r1, 2, , p1从而知方程 1（mod p）有p1个解 x1, 2, , p1（mod p）再由定理3.4.4， p1

21、e，即g的阶为p1。（定理3.4.4：同余方程0（mod p）的解数不超过其次数（mod p）【推论】设p为奇素数，d是p1的正因子，则模p阶为d的元素存在。（证）利用()构造d阶元素。只要选a为原根，选(p-1)/d代入上式的d即可。【定理5.2.2】设g是模p的一个原根，则g或gp是模的原根。【定理5.2.3】设p为奇素数，则对任意正整数，模的原根存在。进一步，若g是模的一个原根，则对任意正整数，g是模的原根。【例】设2，p3，2是模9的一个原根，则2是模27，81，的原根。同理，2是模25的一个原根，所以2也是模125，625，的原根。【定理5.2.4】设1，g是模的一个原根，则g与g中

22、的奇数是模m2的一个原根。【例】设2，p3，2是模9的一个原根，且22，2911故11是模18的一个原根。又7是模25的一个原根，而77，72532，所以7也是50的一个原根。【定理5.2.5】设a是一个奇数，则对任意3，有1（mod ）（本定理说明(a)）【定理5.2.6】设3，则(5)【定理5.2.7】模m的原根存在的充分必要条件是m2，4，2。其中p为奇素数。【定理5.2.8】设m1，(m)的不同素因数是，则g是模m的一个原根的充分必要条件是1（mod m），i1, 2, , k意义 ：给出了一个找原根的方法【例】求模41的所有原根。（解）(m)(41)405，2，5，20，8，故只需验

23、证，1？ （mod 41）验算：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的简化剩余系为1，3，7，9，11，13，17，19，21，23，27，29，31，33，37，39共有(41)(40)16个数，那么原根为6，11，7（mod 41）【例】设模数m1681，求模m的原根。（解）已知6是模41的原根，故由定理5.2.2知，6或64147是模1681的原根。计算1431413（mod ），151814137（mod ）即1（mod ），1（m

24、od ）所以6和47都是模1681的原根（因()16404140）。另由定理5.2.3，6和47是所有模的原根。【例】设模数m23362，求模m的原根。（解）由例2知6和47是模的原根，故由定理5.2.4知，61687和47是模23362的原根。【定理5.2.9】设p为素数，正整数d(p)p1，则对模数p而言，阶为d的数恰有个(d)。（证）见定理5.2.1的第二种证明过程。例p13，(p)12223，其因数有d1, 2, 3, 4, 6, 12故对模数13而言：1阶元素有(1)1个，即a1；2阶元素有(2)1个，即a12-1；3阶元素有(3)2个，即a3, 9；4阶元素有(4)2个，即a5,

25、8；6阶元素有(6)2个，即a4, 10；12阶元素有(12)4个，即a2, 6, 7, 11。【定理5.2.10】设为奇素数，若，则，1, 2, ,都不是的原根。（证）由定理6.1.5，对模的阶为算法：S1：列出备选整数表：1, 2, 3, , S2：选小的正整数，求对的阶。S3：若，则不是原根，那么就在备选整数表中除去以下各数：S4：若备选整数表只剩下个数，则输出表中全部整数（即全部原根）；否则，转S2说明：（1）在S3步，若，则是的原根，即可结束上述过程，利用定理6.1.5的推论获得全部原根。（2）由于奇素数有个原根，故最后剩下的个数肯定是的原根。【例】利用定理6.2.9给出的方法求模4

26、1的所有原根。（解）40，由定理6.1.1的推论，的阶的可能值只有1, 2, 4, 5, 8, 10, 20, 40。16，即23有16个原根。模数23的备选整数表为：1, 2, 3, , 40选2，计算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表中剩余整数为3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 2

27、9, 30, 34, 35, 38再选3，计算401（mod 41），所以8，3不是原根。在备用表中除去（1, 2, , 8）： 3, 9, 27, 40, 38, 32, 14, 1其中1, 9, 32, 40共4个数在第一次已被剔除。此时表中剩下16个数：6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35显然都是原根。对数及n次剩余目的：研究以下同余方程有解的条件和解数：a（mod m），(a, m)1背景问题：设g是模m的一个原根，则当x遍历模(m)的最小正完全剩余系时，遍历模m的一个简化剩余系。故对任意y，(y, m

28、)1，则存在唯一的整数x（1x(m)），使得y（mod m）【例1】：m10，(10)4，其简化剩余系为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时有3，9，7，1（mod m）是10的简化剩余系。故x只需遍历1, 2, 3, 4(10)即可。【例2】：m18，(18)6，18的简化剩余系为1, 5, 7, 11, 13, 17。由(6)2知，模18有两个原根5和11。选g5，则1, 2, 3, 4, 5, 6, 7, , 185，7，17，13，11，1（mod m）是18的简化剩余

29、系。故x只需遍历1, 2, 3, 4, 5, 6(18)即可。定义【定义5.3.1】设g是模m的一个原根，对已知的a，存在整数r，使得式a（mod m） （1）成立，则称r为以g为底的a对模m的一个离散对数（简称为对数），记作r或，。对数也称为指标，记为r或。【例】（利用指数函数和穷举求离散对数）已知5是模17的原根。求5对17的离散对数。（解）先构造以5为底的指数函数表12345678910111213141516a58613142101612911431571再由上表构造离散对数表12345678910111213141516r16613121315210711945148离散对数的性质【

30、定理5.3.1】设m1，g是模m的一个原根，(a, m)1，若整数r使得a（mod m）成立，则r满足r（mod (m)）（证）因为(a, m)1，故a（mod m）从而 1（mod m）又知g模m的阶为(m)，由定理5.1.1知(m)r故 r（mod (m)）【例】已知5是17的一个原根，且r38，那么，计算可得2（mod 17）而6，故386（mod (17)=16）（说明，a的对数的值实质上有无穷多，如对模数17及其原根5而言， 由6（mod (17)16）知，2的对数有6，22，38，54，）（也可以说有同一真数的对数有无穷多）（原因： 2（mod 17）（本质：1（mod 17）【推

31、论】设m1，g是模m的一个原根，(a, m)1，则10（mod (m)），g1（mod (m)）（证）因为1（mod m），g（mod m）【定理5.3.2】设m1，g是模m的一个原根，若(, m)1（1,2,n），则（mod (m)）特别地n（mod (m)）（证）令（i1,2,n），由对数的定义5.3.1（mod m）， i1, 2, , n从而 （mod m）由定理5.3.1， ()r1+r2+rn（mod (m)）即结论成立。【定理5.3.3】设m1，g是模m的一个原根，整数r满足1r(m)，则以g为底的对模m有相同对数r的所有整数全体是模m的一个简化剩余类。（证）因r，(, m)1由

32、对数的定义5.3.1，ara（mod m）故以g为底的对模m有同一对数r的所有整数都属于所在的模m的一个简化剩余类。（说明，对数r的真数a的值实质上有无穷多，如对模数17及其原根5而言， 由2（mod 17）知，对数6对应的真数有2，19，36，53，）（也可以说有同一对数的真数也有无穷多）【例】作模41的对数表。（解）已知6是模41的原根，计算(mod 41)得以6为底的离散对数表y（行标为x的十位数，列表为x的个位数，交叉位置为对数y）012345678904026151222139383018327312537243316923414293613417511732328101819212

33、32356420由此可构造反对数表（即指数函数表，y）：01234567890619112527392910191322842421318263334240355301614212312239133717203823158741【例】设模数m41，分别求整数a29，18以6为底的离散对数。（解）查上例所给离散对数表，可得(28)11，(18)16计算离散对数的复杂度：求离散对数是困难问题。即已知模数m及其一个原根g，当已知某个整数x的指数函数值y（mod m）时，求xy，是NP问题。离散对数的计算Pohlid-Hellman法Pohlid-Hellman（波里德-海尔曼）算法主要是利用原根的性

34、质以及的分解结果，实现离散对数的计算。其中为素数。设和都是正整数，为素数，是的原根。求正整数x，满足设有标准分解式， ，那么，根据中国剩余定理，只要能确定， 则便能求得。即由中国剩余定理可得其中，且（i1, 2, , ）。下面讨论求的方法，其中以为例：由于，故由于，故有，从而有由于是原根，即，故而另一方面（j2, 3, , ），故j1时，有所以将表示为进制，即记，j0, 1, , 那么即那么，比较等式两边就可以确定。但由于等式左边是已知的，而右边的是未知的，故确定的方法是：令0, 1, , ，分别计算，那么，必存在某个（），使得上式成立，即，从而可知。如果，1，则可以确定，即。若2，则需进一步

35、确定等。而一旦确定了，就可以利用它继续确定。因为故若令，就有即 那么，类似于确定的方法，由上式可以确定。同理，若3，可令，则有由上式可以确定。以此类推，可得。另外，由上边的推导过程可以看出，在确定时，每次都要反复用到（0, 1, , ），故为了计算方便，可以令，预先计算好（显然1（mod ），并列表以备使用时直接查表即可。【例6.4.1】设8101，6，y7833。求x使之满足（解）首先有81016135016(1350)1（mod 8101） 13506751（mod 8101）其次，分解得8100对2，有8100（mod 8101），并构造表（见表6.4.1）。表6.4.1 18100对3

36、，有5883（mod 8101），2217（mod 8101），构造表（见表6.4.2）。表6.4.2 158832217对5，有3547（mod 8101），构造表（见表6.4.3）。表6.4.3 1354735670775221（a）2，2：需要分别确定以获得。（a.1）计算8100（mod 8101）查表6.4.1知8100。所以1（a.2）计算783367515356（mod 8101）1（mod 8101）查表6.4.1知1。所以0 1021（b）3，4：需要分别确定以获得。（b.1）计算2217（mod 8101）查表6.4.2知2217。所以2（b.2）计算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最后，计算2025，100，324并分别解同余方程得，。 11202544100641232424（mod 8100）4337（mod 8100） 7833（mod 8101）或4337（mod 8100）最后需要说明的是：由前面的推导过程可以看出，Pohl

38、id-Hellman算法是利用穷举和比较求得，并由其再求得，最终得到问题的答案。故当只有小的素因数时，此算法有效。反之，只要有一个很大的素因数，则使用本算法的意义并不大。因为此时计算（0, 1, , ）的工作量还是很大的。Shank法Shank（商克）法是一种比较有效的算法，不仅速度快，而且需要的存储量也较少。设已知素数p、整数a和y，求x满足， 0 xn其中n是a的乘法周期，即。问题等价于求离散对数。Shank法的运算是在有限域上进行（即是在集合0, 1, 2, ,1上关于模素数的加法和乘法运算，有限域概念见9.4）。其基本思想是：选一整数，设，0rd，故只要求得和r，就等于求出了x。令0,

39、 1, ,，计算，并构造一个指数函数表。为了便于检索，按值的增序排列。由于假定，所以令0, 1, 2, ，逐个计算，直到等于表中某个（）为止。那么，必有，输出。Shank法可以归纳如下，其中已知素数、底数a、真数y和a的乘法周期，且所有运算都在上进行：S1. 选择；0；1S2. 将的值填入指数函数表S3. 若r，则 对表格数据按的值增序排列；转S4 否则 ；转S2 /完成建表S4. 计算：；0 /赋初值S5. 若表中存在一对数，满足，则令；输出；算法结束否则；转S5 /迭代求解【例6.4.2】在GF（23）上求。（解）5的乘法周期为22，故5是23的原根。对于很小的23，可以穷举求解，即计算：

40、1，5，2，19，3。所以。现在用Shank法求解：选，针对0, 1, , d1即0, 1, 2, 3, 4计算，建立指数函数表（见表6.4.4），其中按的增序排列。表6.4.4 (mod 23)的指数函数表12451002413计算，3，0检查：因表中无3，故继续计算：15322，1（即计算的是22）检查：表中无22，继续计算：15228，2（即计算8）检查：表中无8，继续计算：1585，3（即5）检查：表中存在5，对应的1，故有35116 或 另外，若的乘法周期可以分解，则该方法还可化简。思路如下：设（），则的乘法周期为，的乘法周期为。若 （0）则 ，0，0令 由于 即 令 则 由此得时，

41、求的算法如下：S1. ；S2. 求S3. ；S4 . 求S5. 输出 二项同余方程n次剩余二项同余方程：a（mod m）， 1【定义5.5.1】设m1，(a, m)1，若n次同余方程a（mod m） （1）有解，则a叫做对模m的n次剩余；否则，叫做对模m的n次非剩余。【例】求5次同余方程9（mod 41）的解。（解）查模数为41，底数为6的离散对数表，可得(9)30，即9（mod 41）。再令 （mod 41）原方程变为 （mod 41）因6是原根，故由定理5.3.15y30（mod 40(41)） （2）（5, 40）5，且530，故此方程有5个解）即 y6（mod 8）故（2）的解为 y6

42、，14，22，30，38（mod 40） ，39，21，5，9，8（mod 41）故9是模41的5次剩余。【例】求7次同余方程9（mod 41）的解。（解）因为(9)30，即9（mod 41）。再令 （mod 41）原方程变为 （mod 41）6是原根，故有 7y30（mod 40(41)）解之，得 y10（mod 40）故原方程有唯一解 x32（mod 41）【例】求8次同余方程9（mod 41）的解。（解）因为(9)30，即9（mod 41）。再令 （mod 41）原方程变为 （mod 41）6是原根，故有 8y30（mod 40(41)）此方程无解，故原方程无解。【定理5.5.1】设m1

43、，g是模m的一个原根，(a, m)1，则同余方程a（mod m） （3）有解。且在有解的情况下，解数为。（证）若方程（3）有解（mod m）则分别存在非负整数u, r，使得（mod m），a（mod m）由（3）得（mod m）由定理5.3.1知 nur（mod (m)）（可以理解为将方程gnugr（mod m）两边同时以g为底取对数，但要注意取对数后模数变为(m)）即方程 nyr（mod (m)） （4）有解（且解为yu（mod (m)），故（n,(m)）ra反之，若，则方程（4）有解yu（mod (m)）且解数为d(n,(m)。因此，方程（3）有解（mod m）且解数也为d(n,(m)【推

44、论】在定理5.5.1条件下，a是模m的n次剩余的充分必要条件是1（mod m），其中d(n，(m)。（定理5.5.1：设m1，g是模m的一个原根，(a, m)1，则同余方程a（mod m）有解（n,(m)）a。且在有解的情况下，解数为（n,(m)）（证）设a（mod m），若a是模m的n次剩余，即方程a（mod m）有解，再由定理5.5.1知，即dr，所以1（mod m）反之，由1（mod m）知1（mod m）。而g是原根，即g的阶数为(m)，故由定理5.1.1(m)即。【例】解同余方程23（mod 41）。（解）d(n，(m)(8，(41)(8，40)8。查表得 (23)36因为836，故

45、原方程无解。【例】解同余方程37（mod 41）。（解）d(n，(m)(12，(41) )(12，40)4。查表得 (37)32因为432，故方程有4个解。求等价方程，原方程两边同时取对数，得12x37（mod 40）即12x32（mod 40） （5）（即方程12y32（mod 40），对应方程（4）：nyr（mod (m)），此处n12，r32）利用同余性质有3x8（mod 10）解为x6（mod 10）方程（5）的解为x6，16，26，36（mod 40）查离散对数的反函数表（即指数函数表）得原方程的解为，39，18，2，23【定理5.5.2】设m1，g是模m的一个原根，(a, m)1，

46、则a对m的阶数为(a)特别地，a是模m的原根的充分必要条件为(a, (m)1。（证）由定理5.1.4即得。（定理5.1.4：设整数m1，(a, m)1，整数d0，则()）（此处的g即定理中的a，a即定理中的ad，而g是原根（即g的阶数为(m)），故必存在整数r（1r(m)），使得agr（mod m），此处的r即定理中的d，且有ra）【定理5.5.3】设m1，g是模m的一个原根，则模m的简化剩余系中，阶是e的整数共有(e)个。特别地，原根共有(m)个。（证）因m有原根g，由定理5.1.3，知a的阶为(a)()显然，a的阶是e的充分必要条件是e，即(m), d)令d（0e）。则上式等价于（, e）

47、1（否则（, e）1，设（, e）k，则d。而显然有(m)，故(m), d)，矛盾）。而满足（, e）1的显然有(e)个，故阶为(m)的整数个数是(m)，即原根个数为(m)。原根与离散对数的应用DiffieHellman密钥交换算法原根的应用ElGamal加密算法构造全局变量 既可以用于加密，也可以用于签名，其安全性依赖于有限域上计算离散对数的难度 要产生一对密钥，首先选择一素数p，整数模p的一个原根g，随机选取x，g和x都小于p，然后计算：y（mod p） 公开密钥是y，g，p，其中g，p可以为一组用户共享 私有密钥是xElGamal加密算法 将明文信息M表示成 0, 1, , p1 范围内

48、的数 加密: 秘密选择随机数k， 计算： a（mod p） bM（mod p） 密文为(a, b) 解密:M（mod p）其中除法表示乘法b（原理：因（mod p），故M（mod p）（不足：信息有扩张）例 生成密钥：使用者A选取素数p2357及的生成元g2，A选取私钥x1751并计算公钥y（mod p）（mod 2357）1185A的公钥是p2357， g2， y1185 加密：为加密消息M2035， 消息的发送方B选取一个随机整数k1520 并计算a（mod p）215201430（mod 2357）bM（mod p）2035697（mod 2357） （其中（mod p）2084（mod

49、 2357）B发送（a, b）（1430, 697）给A 解密：A计算 872 (mod 2357)Mb697872 2035 (mod 2357)ElGamal加密算法安全性 复杂度：攻击ElGamal加密算法等价于解离散对数问题 要使用不同的随机数k来加密不同的信息 假设用同一个k来加密两个消息，所得到的密文分别为和，则b1/b2M1/M2，故当已知时，可以很容易地计算出来。即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)那么，设已知2035，则有b2/b120359846971100（mod 2357）b3/b1203541269711000（mod 2357）（其中6971700（mod 2357）改进的随机数生成算法利用同余运算生成伪随机数的Lehmer算法（也称线性同余法（LCGS）：， 1, 2, 同时讨论了其安全性。该算法的循环周期严重依赖于乘数、增量和种子值的选择。其实质在于（mod ）即每个完全由m、a、c及决定。故算法关键是如何确定参数m、a、c和。【定理5.6.1】（Hull和Dobell）由Lehmer算法生成的随

51、机数列为满周期数列的充分必要条件是（）1；（）若存在素数，使得，则必有；（）若，则必有。（证）（略）。条件（）意味着c和m互素。条件（）是指1即若，则可得其中q为m的素因数。由条件（），若为整数，可设获得满周期或足够长的周期是对所有随机数生成算法的重要考量指标之一。其中较常见的有混合线性同余法（Mixed LCGS，选0）和乘法线性同余法（Multi plicative LCGS，c0）。（1）混合线性同余法对于0，有可能使得周期T=m。此处仅讨论如何选择m。为得到尽可能大的周期，以及在（0, 1）区间内的高密度的随机数，故希望m尽可能大。其次，利用除以而获得余数，是一项十分缓慢的算法操作。故

52、为了避免这种除法操作，较好的选择是，其中b为计算机用于存放实际数值的字长，这样就就能够利用整数溢出来避免这种明显的除以m的操作。可供选用的混合线性同余法有（）；（）。（2）乘法线性同余法本方法的优点在于不需要（0）。由于条件（）不能满足，因而不能达到满周期。但仍可以适当选择与，使。此方法是比较有效的方法，也是线性同余法中被采用得较多的方法。Hutchinson建议取小于的最大素数。那么，对于素数而言，可以证明，如果是以为模的素因数，则周期。显然，这只要选为的原根，且1即可，这时在每一个循环里，严格地获得每个整数1, 2, , 各一次，而且选为从1至之间的任意整数，都能保证。这种方法称为素数模乘

53、法线性同余法（PMMLCGs）。对于方法PMMLCGs，由于不能选为模，因而不能运用溢出的机理去影响除法的模。针对此情况，Payne、Rabung和Bogyo等人提出了一种避免明显除法，运用溢出原理的方法模拟除法。由 知 ，令 若 ，则 若 ，则令数列提供了时的随机序列，并且遵从原则式中可由移模减数而得。PMMLCGs的实际用例：35，小于的最大素数为，且时3125，生成的随机数具有较好的特性；对于35，小于的最大素数为，且两种得到广泛应用的关于的选择为：16807和。（3）Fibonacci法此方法是建立在Fibonacci（斐波那契）数列的基础上，其递归公式为， 1, 2, Fibonac

54、ci法需要两个初值和。其得到的周期有可能大于，但它所生成的序列的随机性较差，故不能提供满意的结果。（4）二次同余法由Coveyon提出的二次同余法近似相当于双精度的中间平方法，但却比后者有较长的周期。其递归公式为， 1, 2, 一种快速傅里叶变换算法【定义6.6.1】离散傅里叶变换（DFT）：Fourier变换矩阵，另法表示：运算量：次复数乘法和次复数加法【定义6.6.2】设和是两个周期为的序列，其互相关函数定义为，0, 1, 2, , 【定理6.6.2】设是一个奇素数，则式（5.6.1）可化为两个周期为的序列的互相关函数，和次加法来计算。（证）设，1, 2, , （5.6.2）则有，1, 2

55、, , （5.6.3）又设是的一个原根，则1, 2, , 可表为（0, 1, , ），即除以的最小非负余数，于是式（5.6.2）化为，0, 1, , （5.6.4）由于是原根，所以式（5.6.4）是两个周期为的序列（0, 1, ）和（0, 1, ）的互相关函数，再由式（5.6.3）的次加法给出全部。同理，对于和2（是一个奇素数），也有类似的结果。同余方程的求解【例6.6.3】解同余方程169（mod 41）。（解）此处利用离散对数求解。已知6是41的原根，故对方程两边取以6为底的对数，有再由定理6.3.2，方程可表为查离散对数函数表6.3.4有，代入上式得24 再查指数函数表6.3.3得39（

56、mod 41）。所以原方程的解为39（mod 41）利用离散对数还可以解幂同余方程，1 （6.6.5）其中m有原根g。【定理6.6.3】设整数m1，其原根为g。那么，幂同余方程（6.6.5）有解的充分必要条件是 （6.6.6）记，如果方程有解，则其解数为其通解为，（证）由于m有原根g，故等式（6.6.5）两边针对模数m取以g为底的对数，有 （6.6.7）显然幂同余方程（6.6.5）与一次同余方程（6.6.7）同时有解或无解，且解数也相同。而方程（6.6.7）为一次同余方程，故由定理4.4.2可推导出本定理的所有结论。【例6.6.4】判断幂同余方程2（mod 17）是否有解，若有解，请求其解。（

57、解）16，查表6.3.2知7，6，（16, 7）1，显然方程有解。由例6.1.4知5是17的一个原根，对方程两边取以5为底的对数即7x6（mod 16）解之得，即为原方程的解。【例6.6.5】判断幂同余方程16（mod 17）是否有解，若有解，请求其解。（解）查表6.3.2得12，8，（16, 12）4，且，所以方程有解。对方程两边取以5为底的对数得一次同余方程12x8（mod 16）解之得2, 6, 10, 14（mod 16），即为原方程的解。比较例6.6.4和例6.6.5，一个为单解，一个为多解，其本质原因在于指数函数的底数10是17的原根，故对应真数2，使得2（mod 17）成立的模16不同余的x只能有一个，而后者中函数的底数4不是原根，其对模数17的阶为4，故对模数4来说，其解为1；而对模数16来说，其不同余的解则为4个。单向函数单向函数（1）给定x，计算yf(x)是容易的；（2）给定y， 计算x是不可行的。例如：对给定的g，已知x，计