《《数论算法》教案-5章(原根与离散对数)(共57页).doc》由会员分享，可在线阅读，更多相关《《数论算法》教案-5章(原根与离散对数)(共57页).doc（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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
3、。且1，1，1，1，1，1（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
4、)1，d为正整数，则1（mod 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、5)、(7)的值。（解）(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，且
6、2和3是原根。（证）由推论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，验
7、证推论2。（解）首先，直接计算知：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）的充分必要条件是
8、1（mod m）【例7】已知整数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的简化剩余系。（解）直接
9、计算得k012345678910111213141515861314210161291143157【例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）
10、 由定理5.1.2的证明过程知， 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（mo
11、d m）由定理5.1.1，()，所以 ()【例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
12、.1.2知(m)个数g，是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。【推
13、论】设m1，且m有原根，设(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
14、)(b)反之，若(ab) (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, 3
15、7, 39, 41, 43, 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)
16、(a)，(a)(a)从而由最小公倍数性质知 (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）（注
17、意为整数）即 a（mod 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)，
18、(9)【定理5.1.8】设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)
19、 (b, m) 1，则存在整数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) 363
20、0235，(17)121025由定理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
21、, 2, , p1（mod 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，的
22、原根。【定理5.2.4】设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的所有原
23、根。（解）(m)(41)405，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
24、），151814137（mod ）即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阶元素有
25、(3)2个，即a3, 9；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,
27、17, 19, 22, 24, 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遍历模(
28、m)的最小正完全剩余系时，遍历模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,
29、 7, , 185，7，17，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再由上表构造离散对数表12345678910111
30、213141516r16613121315210711945148(三) 离散对数的性质【定理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)，则以
32、g为底的对模m有相同对数r的所有整数全体是模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）012345678904026151222139383018327
33、31253724331692341429361341751173232810181921232356420由此可构造反对数表（即指数函数表，y）：01234567890619112527392910191322842421318263334240355301614212312239133717203823158741【例】设模数m41，分别求整数a29，18以6为底的离散对数。（解）查上例所给离散对数表，可得(28)11，(18)16计算离散对数的复杂度：求离散对数是困难问题。即已知模数m及其一个原根g，当已知某个整数x的指数函数值y（mod m）时，求xy，是NP问题。5.4 离散对数的计算
34、5. 4. 1 Pohlid-Hellman法Pohlid-Hellman（波里德-海尔曼）算法主要是利用原根的性质以及的分解结果，实现离散对数的计算。其中为素数。设和都是正整数，为素数，是的原根。求正整数x，满足设有标准分解式， ，那么，根据中国剩余定理，只要能确定， 则便能求得。即由中国剩余定理可得其中，且（i1, 2, , ）。下面讨论求的方法，其中以为例：由于，故由于，故有，从而有由于是原根，即，故而另一方面（j2, 3, , ），故j1时，有所以将表示为进制，即记，j0, 1, , 那么即那么，比较等式两边就可以确定。但由于等式左边是已知的，而右边的是未知的，故确定的方法是：令0,
35、1, , ，分别计算，那么，必存在某个（），使得上式成立，即，从而可知。如果，1，则可以确定，即。若2，则需进一步确定等。而一旦确定了，就可以利用它继续确定。因为故若令，就有即 那么，类似于确定的方法，由上式可以确定。同理，若3，可令，则有由上式可以确定。以此类推，可得。另外，由上边的推导过程可以看出，在确定时，每次都要反复用到（0, 1, , ），故为了计算方便，可以令，预先计算好（显然1（mod ），并列表以备使用时直接查表即可。【例6.4.1】设8101，6，y7833。求x使之满足（解）首先有81016135016(1350)1（mod 8101） 13506751（mod 8101）
36、其次，分解得8100对2，有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：需要分别确定以获
37、得。（b.1）计算2217（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
38、） 7833（mod 8101）或4337（mod 8100）最后需要说明的是：由前面的推导过程可以看出，Pohlid-Hellman算法是利用穷举和比较求得，并由其再求得，最终得到问题的答案。故当只有小的素因数时，此算法有效。反之，只要有一个很大的素因数，则使用本算法的意义并不大。因为此时计算（0, 1, , ）的工作量还是很大的。5. 4. 2 Shank法Shank（商克）法是一种比较有效的算法，不仅速度快，而且需要的存储量也较少。设已知素数p、整数a和y，求x满足， 0xn其中n是a的乘法周期，即。问题等价于求离散对数。Shank法的运算是在有限域上进行（即是在集合0, 1, 2, ,1上关于模素数的加法和乘法运算，有限域概念见9.4）。其基本思想是：（1） 选一整数，设，0rd，故只要求得和r，就等于求出了x。（2） 令0, 1, ,，计算，并构造一个指数函数表。为了便于检索，按值的增序排列。（3） 由于假定，所以