Pohig-Hellman演算法求解離散對數問題

離散對數(DLP)問題：
a x ≡ b ( m o d p ) a^{x} \equiv b \pmod{p} ax≡b(modp)
p p p是大素數，

前面已經介紹了求解離散對數問題的小步大步演算法(BSGS)(時間復雜度是 O ( p ) O(\sqrt{p}) O(p ?))，這里介紹另外一種求解光滑階回圈群上的離散對數的方法——Pohig-Hellman方法，事實上，Pohlig-Hellman演算法的復雜度在一般情況下比BSGS演算法高！但是在特殊情況下(回圈群的階是光滑數，即可以因子分解成較小的數的乘積)，使用Pohlig-Hellman能取得好的效果，而且有些時候，盡管BSGS能夠將復雜度降至 p \sqrt{p} p ?，但是這個數依然很大，所以不能用，這時我們可以考慮Pohig-hellman方法能不能起作用，

演算法思想

考慮上述DLP問題，因為 p p p是大素數，模 p p p的回圈群的階是 p ? 1 p-1 p?1，假設模 p p p的最小的本原元是 g g g（本原元是可以求的），那么有
a ≡ g a ′ ( m o d p ) b ≡ g b ′ ( m o d p ) a\equiv g^{a'}\pmod{p}\\ b\equiv g^{b'}\pmod{p} a≡ga′(modp)b≡gb′(modp)
進一步有
a x ≡ b ( m o d p ) ?? ? ?? g a ′ x ≡ g b ′ ( m o d p ) a^{x} \equiv b\pmod{p} \iff g^{a'x}\equiv g^{b'} \pmod{p}\\ ax≡b(modp)?ga′x≡gb′(modp)
有
a ′ x ≡ b ′ ( m o d p ? 1 ) a'x \equiv b' \pmod{p-1} a′x≡b′(modp?1)
如果我們求出了滿足上式的 a ′ a' a′和 b ′ b' b′，通過擴展的gcd方法可以求一次同余方程的解得到 x x x，

問題歸結成如何求 a ′ a' a′和 b ′ b' b′，即原本的一個離散對數問題，現在變成兩個離散對數問題：
a ≡ g a ′ ( m o d p ) b ≡ g b ′ ( m o d p ) a\equiv g^{a'}\pmod{p}\\ b\equiv g^{b'}\pmod{p} a≡ga′(modp)b≡gb′(modp)

如何求解 a ′ a' a′和 b ′ b' b′

以求 a ′ a' a′為例，解DLP問題： g x ≡ a ( m o d p ) g^{x}\equiv a \pmod{p} gx≡a(modp)

1. 將 p ? 1 p-1 p?1進行標準的素因子分解，即 p ? 1 = ∏ i = 1 m p i k i = p 1 k 1 p 2 k 2 p 3 k 3 ? p m k m p-1=\prod \limits_{i=1}^{m}p_{i}^{k_{i}}=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\cdots p_{m}^{k_{m}} p?1=i=1∏m?piki??=p1k1??p2k2??p3k3???pmkm??

2. 對每個素因子 p i p_{i} pi?，將 x x x表示成 p i p_{i} pi?進制，有 x = a 0 + a 1 p i + a 2 p i 2 + a 3 p i 3 + ? + a k i ? 1 p i k i ? 1 ( m o d p i k i ) x=a_{0}+a_{1}p_{i}+a_{2}p_{i}^{2}+a_{3}p_{i}^{3}+\cdots+a_{k_{i}-1}p_{i}^{k_{i}-1} \pmod{p_{i}^{k_{i}}} x=a0?+a1?pi?+a2?pi2?+a3?pi3?+?+aki??1?piki??1?(modpiki??)，這樣的 p i p_{i} pi?進制表示，系數 a i a_{i} ai?自然是小于 p i p_{i} pi?

3. 令 r = 1 r=1 r=1，有
   ( g x ) p ? 1 p i r ≡ a p ? 1 p i r ( m o d p ) \left( g^{x} \right)^{\frac{p-1}{p_{i}^{r}}}\equiv a ^{\frac{p-1}{p_{i}^{r}}} \pmod{p} (gx)pir?p?1?≡apir?p?1?(modp)
   展開 x x x有
   ( g a 0 + a 1 p i + a 2 p i 2 + a 3 p i 3 + ? + a k i ? 1 p i k i ? 1 ) p ? 1 p i r ≡ a p ? 1 p i r ( m o d p ) g a 0 ? p ? 1 p i × g a 1 ( p ? 1 ) × g a 2 ( p ? 1 ) p i × ? × g a k i ? 1 ( p ? 1 ) p i k i ? 2 ≡ a p ? 1 p i ( m o d p ) \left( g^{a_{0}+a_{1}p_{i}+a_{2}p_{i}^{2}+a_{3}p_{i}^{3}+\cdots+a_{k_{i}-1}p_{i}^{k_{i}-1} } \right)^{\frac{p-1}{p_{i}^{r}}}\equiv a ^{\frac{p-1}{p_{i}^{r}}} \pmod{p}\\ g^{a_{0}* \frac{p-1}{p_{i}}}\times g^{a_{1}(p-1)} \times g^{a_{2}(p-1)p_{i}}\times \cdots \times g^{a_{k_{i}-1}(p-1)p_{i}^{k_{i}-2}}\equiv a ^{\frac{p-1}{p_{i}}} \pmod{p} (ga0?+a1?pi?+a2?pi2?+a3?pi3?+?+aki??1?piki??1?)pir?p?1?≡apir?p?1?(modp)ga0??pi?p?1?×ga1?(p?1)×ga2?(p?1)pi?×?×gaki??1?(p?1)piki??2?≡api?p?1?(modp)
   注意從第二項開始，每一項指數都包含 p ? 1 p-1 p?1（由費馬小定理知 g p ? 1 ≡ 1 ( m o d p ) g^{p-1} \equiv 1\pmod{p} gp?1≡1(modp)），所以式子變成
   g a 0 ? p ? 1 p i ≡ a p ? 1 p i ( m o d p ) g^{a_{0}* \frac{p-1}{p_{i}}} \equiv a ^{\frac{p-1}{p_{i}}} \pmod{p} \\ ga0??pi?p?1?≡api?p?1?(modp)
   這個式子中只有 a 0 a_{0} a0?是未知的，因為 a 0 ∈ [ 0 , p i ? 1 ] a_{0} \in \left[ 0,p_{i}-1 \right] a0?∈[0,pi??1]，所以可以窮舉得到 a 0 a_{0} a0?的值，

4. 再令 r = 2 、 3 、 4 、 ? 、 k i r=2、3、4、\cdots 、k_{i} r=2、3、4、?、ki? ，重復步驟3，依次窮舉求出 a 1 ， a 2 ， ? ? , a k i ? 1 a_{1}，a_{2}，\cdots ,a_{k_{i}-1} a1?，a2?，?,aki??1?，整個的時間復雜度是 O ( p i k i ) O(p_{i}k_{i}) O(pi?ki?)，那么可以的到
   x = a 0 + a 1 p i + a 2 p i 2 + a 3 p i 3 + ? + a k i ? 1 p i k i ? 1 ( m o d p i k i ) x=a_{0}+a_{1}p_{i}+a_{2}p_{i}^{2}+a_{3}p_{i}^{3}+\cdots+a_{k_{i}-1}p_{i}^{k_{i}-1} \pmod{p_{i}^{k_{i}}} x=a0?+a1?pi?+a2?pi2?+a3?pi3?+?+aki??1?piki??1?(modpiki??)

5. 重復上述程序，得到 m m m個關于 x x x的式子，利用中國剩余定理(CRT)，可以計算出 x x x的值，

利用這個方法求出 a ′ a' a′和 b ′ b' b′后，就可以得到原DLP問題的解，

舉例

關于舉例和代碼可以看這個博客離散對數問題——pohlig-hellman演算法講解(有例子)，

Q&A

1. 但是看完這個演算法的流程之后，我就產生一個問題：為什么要先把 a x ≡ b ( m o d p ) a^{x}\equiv b\pmod{p} ax≡b(modp)轉化成

a ≡ g a ′ ( m o d p ) b ≡ g b ′ ( m o d p ) a\equiv g^{a'}\pmod{p}\\ b\equiv g^{b'}\pmod{p} a≡ga′(modp)b≡gb′(modp)
計算出 a ′ a' a′和 b ′ b' b′之后再得到 x x x？直接利用后面的方法求出 x x x不行嗎？

答：Pohig-Hellman演算法最重要的點是利用了原根的性質，它只能解決 a ≡ g x ( m o d p ) a\equiv g^{x}\pmod{p} a≡gx(modp)（ g g g是原根）的問題，對于 g g g不是原根的情況，需要利用原根將原方程轉化成兩個關于原根的離散對數問題，為什么呢？

可以看演算法中，在利用 p i p_{i} pi?進制表示之后，得到了
g a 0 ? p ? 1 p i ≡ a p ? 1 p i ( m o d p ) g^{a_{0}* \frac{p-1}{p_{i}}} \equiv a ^{\frac{p-1}{p_{i}}} \pmod{p} ga0??pi?p?1?≡api?p?1?(modp)
這個式子，然后窮舉得到 a 0 a_{0} a0?的值，如果 g g g不是原根，則有 g g g的階不會是 p ? 1 p-1 p?1，可能有 g p ? 1 p i ≡ 1 ( m o d p ) g^{\frac{p-1}{p_{i}}} \equiv 1 \pmod{p} gpi?p?1?≡1(modp)，這樣無論 a 0 a_{0} a0?取何值，式子始終成立，無法求出 a 0 a_{0} a0?，演算法就失效了，

2. 注意Pohig-hellman只能用于求解光滑階群，也就是 p ? 1 p-1 p?1可以分解成小的素因子乘積，否則，窮舉 a i a_{i} ai?的時間復雜度依舊很高，另外可以考慮在窮舉 a i a_{i} ai?時利用小步大步演算法，進一步優劃演算法復雜度，