為什麼有不同版本的 Pohlig-Hellman 攻擊？
我想我對橢圓曲線上的 Pohlig-Hellman 攻擊有所了解。來自初學者配對的第 31 頁：
查找組訂單 $ #E(\mathbb{F}_q) $ ， 叫它 $ n $ ，並將其分解。例子： $ 966 = 2 \cdot 3 \cdot 7 \cdot 23 $
對於每個主要因素 $ p_i $ , 上面：乘以生成器 $ P $ 和目標點（不確定術語是什麼）， $ Q $ ， 經過 $ n/p_i $ （輔因子）
- 這個特定的例子沒有任何被提升到冪的素因數，（例如，分解不是 $ 2^3 \cdot 5^2 $ ，但你乘以 $ n $ 除以素數，而不是素數的指數）
現在我們有 $ [\frac{n}{p_i}]P $ 和 $ [\frac{n}{p_i}]Q $ .
我們知道順序 $ [\frac{n}{p_i}]P $ 是 $ p_i $
因此， $ [\frac{n}{p_i}]Q = [k \text{ mod } p_i]P $ 在哪裡 $ kP = Q $
我們解決 $ k\text{ mod } p_i $ 並為每個重複 $ p_i $
然後，利用中國剩餘定理，我們可以找到 $ k\text{ mod } n $
這一切都大致有道理。它還與本網站上對 Pohlig-Hellman 的其他解釋相匹配：Pohlig-Hellman 算法。
但是，我很困惑 b/c 似乎“完整”的 Pohlig-Hellman 攻擊涉及代表 $ k_i $ 作為 $ z_0 + z_1p_i + z_2p_i^2 + … $
為什麼 Pohlig-Hellman 算法有多種變體？
實際上，使用中國剩餘定理的方法是更通用的版本。代表的那個 $ k_i $ 作為 $ z_0 + z_1p_i + z_2p_i^2 + … $ 僅在群階是素冪（的冪 $ p_i $ )，所以你首先解決每個較小的權力並建立起來。當組不是同一個素數的所有冪時，您使用 CRT（或兩者的混合）。在這兩種情況下，想法都是相同的——在較小的子組中求解 DLP，並使用該資訊在整個組中重建解決方案。