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