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

1、第 5 章 原根与离散对数内容1. 整数的阶2. 原根3. 有原根的整数4. 离散对数（指标）要点1. 原根及其意义2. 有原根的整数的条件3. 离散对数及其性质5.1 阶及其基本性质准备知识：（1） 欧拉定理：m1，(a, m)1，则1（mod m）（2） 问题：是否是使得上式成立的最小正整数？该最小正整数有何性质？(一) 阶和原根概念【定义5.1.1】设m1，(a, m)1，则使得1（mod m）成立的最小正整数e叫做a对模m的阶（或指数），记作(a)。若a的阶e，则a叫做模m的原根。(二) 应用：DiffieHellman密钥交换算法公钥算法的核心：（1） 仅依赖公开信息不足以对算法构成

2、威胁；（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）例：l 素数q353，原根3l A选97， 计算40 mod 353l B选233， 计算248 mod 353l A与B交换l A计算密钥 K160 mod 353l B计算密钥 K160 mod 353(三) 用定义求阶和原根【例1】（按定义求阶和原根）m7，则(7)6。且1，1，1，1，1，1

3、（mod 7）故对模数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（m

4、od m） (a) d即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)的值。（解）(

5、33)20。只需计算、（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是原根。（证）由推论

6、1，(a)(p)p12，故(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。（解）首先，直接

7、计算知：1，3，4，5，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】已

8、知整数39模17的阶为(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的简化剩余系。（解）直接计算得k012345678

9、910111213141515861314210161291143157【例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的证明过

10、程知， r，即dk（mod (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，

11、()，所以 ()【例12】已知(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，是

12、m的一个简化剩余系。而使得（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有原根，设

13、(m)，0，i1,2,k则当(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)

14、(a)(b)，那么1（mod 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

15、, 47, 51, 53, 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)从而由

16、最小公倍数性质知 (a)，(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

17、p）同理有 a（mod 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】设

18、m，n都是大于1的整数，(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，则存在

19、整数c，使得(c)(a)，(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)1210

20、25由定理5.1.9，取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 原根存在的存在性与计算方法【定理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

21、 p）再由定理3.4.4， p1e，即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】设

22、1，g是模的一个原根，则g与g中的奇数是模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)4

23、05，2，5，20，8，故只需验证，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（m

24、od ）即1（mod ），1（mod ）所以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；

25、4阶元素有(4)2个，即a5, 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）由于奇素数有个原根，故最后剩下的个数肯定是的原根。【例】利

26、用定理6.2.9给出的方法求模41的所有原根。（解）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, 2

27、4, 26, 27, 28, 29, 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显然都是原根。5.3 对数及n次剩余目的：研究以下同余方程有解的条件和解数：a（mod m），(a, m)1(一) 背景问题：设g是模m的一个原根，则当x遍历模(m)的最小正完全剩余系时，

28、遍历模m的一个简化剩余系。故对任意y，(y, m)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，1

29、7，13，11，1（mod m）是18的简化剩余系。故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再由上表构造离散对数表12345678910111213141516r166

30、13121315210711945148(三) 离散对数的性质【定理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，）（也可以说有同一真数的对数有无

31、穷多）（原因： 2（mod 17）（本质：1（mod 17）【推论】设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

32、的所有整数全体是模m的一个简化剩余类。（证）因r，(, m)1由对数的定义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）0123456789040261512221393830183273125372433169

33、2341429361341751173232810181921232356420由此可构造反对数表（即指数函数表，y）：01234567890619112527392910191322842421318263334240355301614212312239133717203823158741【例】设模数m41，分别求整数a29，18以6为底的离散对数。（解）查上例所给离散对数表，可得(28)11，(18)16计算离散对数的复杂度：求离散对数是困难问题。即已知模数m及其一个原根g，当已知某个整数x的指数函数值y（mod m）时，求xy，是NP问题。5.4 离散对数的计算5. 4. 1 Pohli

34、d-Hellman法Pohlid-Hellman（波里德-海尔曼）算法主要是利用原根的性质以及的分解结果，实现离散对数的计算。其中为素数。设和都是正整数，为素数，是的原根。求正整数x，满足设有标准分解式， ，那么，根据中国剩余定理，只要能确定， 则便能求得。即由中国剩余定理可得其中，且（i1, 2, , ）。下面讨论求的方法，其中以为例：由于，故由于，故有，从而有由于是原根，即，故而另一方面（j2, 3, , ），故j1时，有所以将表示为进制，即记，j0, 1, , 那么即那么，比较等式两边就可以确定。但由于等式左边是已知的，而右边的是未知的，故确定的方法是：令0, 1, , ，分别计算，那么

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

36、有8100（mod 8101），并构造表（见表6.4.1）。表6.4.1 18100对3，有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

37、（mod 8101）查表6.4.2知2217。所以2（b.2）计算3593（mod 8101）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 81

38、01）或4337（mod 8100）最后需要说明的是：由前面的推导过程可以看出，Pohlid-Hellman算法是利用穷举和比较求得，并由其再求得，最终得到问题的答案。故当只有小的素因数时，此算法有效。反之，只要有一个很大的素因数，则使用本算法的意义并不大。因为此时计算（0, 1, , ）的工作量还是很大的。5. 4. 2 Shank法Shank（商克）法是一种比较有效的算法，不仅速度快，而且需要的存储量也较少。设已知素数p、整数a和y，求x满足， 0xn其中n是a的乘法周期，即。问题等价于求离散对数。Shank法的运算是在有限域上进行（即是在集合0, 1, 2, ,1上关于模素数的加法和乘法

39、运算，有限域概念见9.4）。其基本思想是：（1） 选一整数，设，0rd，故只要求得和r，就等于求出了x。（2） 令0, 1, ,，计算，并构造一个指数函数表。为了便于检索，按值的增序排列。（3） 由于假定，所以（4） 令0, 1, 2, ，逐个计算，直到等于表中某个（）为止。那么，必有，输出。Shank法可以归纳如下，其中已知素数、底数a、真数y和a的乘法周期，且所有运算都在上进行：S1. 选择；0；1S2. 将的值填入指数函数表S3. 若r，则 对表格数据按的值增序排列；转S4 否则 ；转S2 /完成建表S4. 计算：；0 /赋初值S5. 若表中存在一对数，满足，则令；输出；算法结束否则；转

40、S5 /迭代求解【例6.4.2】在GF（23）上求。（解）5的乘法周期为22，故5是23的原根。对于很小的23，可以穷举求解，即计算：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 或 另外，若的乘法

41、周期可以分解，则该方法还可化简。思路如下：设（），则的乘法周期为，的乘法周期为。若 （0）则 ，0，0令 由于 即 令 则 由此得时，求的算法如下：S1. ；S2. 求S3. ；S4 . 求S5. 输出 5.5 二项同余方程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是原根，故由

42、定理5.3.15y30（mod 40(41)） （2）（5, 40）5，且530，故此方程有5个解）即 y6（mod 8）故（2）的解为 y6，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）。再令

43、（mod 41）原方程变为 （mod 41）6是原根，故有 8y30（mod 40(41)）此方程无解，故原方程无解。【定理5.5.1】设m1，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

44、)）ra反之，若，则方程（4）有解yu（mod (m)）且解数为d(n,(m)。因此，方程（3）有解（mod m）且解数也为d(n,(m)【推论】在定理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)，故由定理

45、5.1.1(m)即。【例】解同余方程23（mod 41）。（解）d(n，(m)(8，(41)(8，40)8。查表得 (23)36因为836，故原方程无解。【例】解同余方程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

46、 40）查离散对数的反函数表（即指数函数表）得原方程的解为，39，18，2，23【定理5.5.2】设m1，g是模m的一个原根，(a, m)1，则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）1（否则（, e）1，设（, e）k，则d。而显然有(m)，故(m), d)，矛盾）。而满足（, e）1的显然有(e)个，故阶为(m)的整数个数是(m)，即原根个数为(m)。5.