《数论算法》 第五章 原根与离散对数
≡g≡gr11?p?1?p1gr12?p?1??gr1??1?1??1?3?p?1?p1
r11?p?1?p12p1即 ?z1?那么，类似于确定r10的方法，由上式可以确定r11。
111?p?1??modp? r?p?1?p?g?modp?
?r11p1z?zg同理，若?1?3，可令2，则有 1gr1?r10?r11p1?g2r12p1+??r1??p1?1?1r?1?1
p1?z2??p?1?3p1=gr1?r10?r11p1???p?1?3p1≡g12?p?1??modp?
由上式可以确定r12。
以此类推，可得r13,r14,?,r1??1?1?。
另外，由上边的推导过程可以看出，在确定
r10,r11,?,r1??1?1?时，每次都要反复用到
p1gi?p?1?p1?g??p?1??i?modp?（i＝0, 1, …,
p?1?p1，故为p1?1）
?了计算方便，可以令?1?g，预先计算好
），并列p）
?1,?12,?,?1p?1（显然?10?g0??p?1?1p1≡1（mod
表以备使用时直接查表即可。
【例6.4.1】设p＝8101，g＝6，y＝7833。求x使之满足
y?gx?modp?
（解）首先有
8101＝6×1350＋1 6(－1350)≡1（mod 8101）
∴ 6?1≡－1350≡6751（mod 8101） 其次，分解p?1得
p?1＝8100＝223452
?6对p1＝2，有?1?g并构造?1i表（见表6.4.1）。
表6.4.1 ?1i
33/58
?p?1?p181002≡8100（mod 8101），
《数论算法》 第五章 原根与离散对数
?10 ?1 1 8100
2?6对p2＝3，有?2?g≡5883（mod 8101），，构造?2i表（见表6.4.2）。 ?22?58832≡2217（mod 8101）
?p?1?p81003
表6.4.2 ?2i ?20 ?2 ?22 1 5883 2217 对p3＝5，有?3?g?p?1?p?681005≡3547（mod 8101），构造?3i表（见表6.4.3）。
表6.4.3 ?3i ?30 ?3 ?32 ?33 ?34 1 3547 356 7077 5221
（a）p1＝2，?1＝2：需要分别确定r10,r11以获得
3r1=r10+r11?2。
（a.1）计算
y?p?1?p1?783381002?78334050≡8100（mod 8101）
查表6.4.1知8100＝?1。所以
r10＝1
（a.2）计算
z1?yg?r10?7833?6?1≡7833×6751≡5356（mod 8101）
?z1??p?1?2p1?5356810022≡1（mod 8101）
查表6.4.1知1＝?10。所以
r11＝0
∴ r1＝1＋0×2＝1
（b）p2＝3，?2＝4：需要分别确定r20,r21,r22,r23以获
23r=r+r?3+r?3+r?3得22021。 2223（b.1）计算
y?p?1?p2?783381003?78332700≡2217（mod 8101）
34/58
查表6.4.2知2217＝?22。所以
《数论算法》 第五章 原根与离散对数
r20＝2
（b.2）计算
z1?yg?r20?7833?6?2?7833?67512≡3593（mod 8101）
?z1??p?1?2p2?3593810032?3593900≡2217（mod 8101）
查表6.4.2知2217＝?22。所以
r21＝2
（b.3）再算
z2?z1g?r21p2?3593?6?2?3?3593?67516≡3708（mod
8101）
?z2??p?1?3p2?3708810033?3708300≡5883（mod 8101）
r22＝1
∴
（b.4）再算
z3?z2g2?r22p2?3708?6?1?32?3708?67519≡6926（mod
8101）
?z3??p?1?4p2?6926810034?6926100≡5883（mod 8101）
∴ r23＝1
∴ r2＝2＋2×3＋1×32＋1×33＝44
（c）p3＝5，?3＝2
y?p?1?p3?783381005?78331620≡356（mod 8101）
∴
r30＝2
z1?yg?r30?7833?6?2?7833?67512≡3593（mod
8101）
?z1??p?1?2p3?3593810052?3593324≡356（mod 8101）
∴ r31＝2
∴ r3＝2＋2×5＝12
最后，计算
?1M1=?p?1?p1=3452＝2025，
?2M2=?p?1?p2=2252＝100，
?3M3=?p?1?p3=2234＝324
35/58
《数论算法》 第五章 原根与离散对数
并分别解同余方程
M1M1?1?2025M1?1?1?mod22?
?1?1M2M2?100M2?1?mod34?
M3M3?1?324M3?1?1?mod52?
得
M1?1?1?mod22?，
?1M2?64?mod34?，
M3?1?24?mod52?。
∴
?1x?1rMM11??1rM?22M2?1rMM33?m3od??1 p≡1×1×2025＋44×100×64＋12×324×24
（mod 8100）
≡4337（mod 8100）
∴ 64337≡7833（mod 8101）或dlog67833≡4337（mod 8100）
最后需要说明的是：由前面的推导过程可以看出，Pohlid-Hellman算法是利用穷举和比较求得r1j，并由其再求
?k?1?2p2?pk得r1，最终得到问题的答案x。故当p?1?p1只有
小的素因数时，此算法有效。反之，只要p?1有一个很大的素因数q，则使用本算法的意义并不大。因为此时计算
??gij??p?1?pj?i?modp?（i＝0, 1, …, q）的工作量还是
很大的。 5. 4. 2 Shank法
Shank（商克）法是一种比较有效的算法，不仅速度快，而且需要的存储量也较少。
设已知素数p、整数a和y，求x满足
y?ax?modp?， 0?x＜n
其中n是a的乘法周期，即a?1?modp?。
问题等价于求离散对数x?dlogp,ay。
nShank法的运算是在有限域GF?p?上进行（即是在集合Zp36/58