《数论算法》 第五章 原根与离散对数
≡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。所以
《数论算法》