Discrete-Logarithm
為什麼索引演算有效？
我了解指數微積分算法的工作原理 - 我知道並了解這些步驟。我了解這些步驟是如何得出的。但是，我無法弄清楚它為什麼起作用。
我可以理解為什麼 Pohlig-Hellman 有效 - PH 減少了離散登錄的計算 $ G $ 計算素數階子群中的離散對數 $ ⟨G⟩ $ . PH 算法允許您在較小的子組中求解 DLP，然後使用中國剩餘定理組合解決方案以獲得原始 DLP 的解決方案。我正在為索引演算尋找類似的理論解釋
為什麼索引演算可以解決 DLP？
索引演算基於兩個簡單的想法：
- 每個整數都可以寫成素數的乘積。
- 一個包含少量變數的線性方程組可以用足夠多的獨立方程來求解。
以循環群為例 $ \mathbb{Z}/p $ 和 $ p $ 一個素根和原根 C. 要素 $ c^i $ （為了 $ i=0,1,2,…,p-1 $ ) 與整數模 p 一致 $ 1,2,…,p-1 $ . 這些整數可以用少數素數的冪來表示 $ P_1,…, P_k $ 小於 $ p $ . 如果我們知道每個素數的索引，那麼，因為索引是加法模 $ p-1 $ ，那麼我們就知道了我們組中每個元素的索引。
所以在這個例子中，變數是素數的索引 $ P_j $ 方程由下式給出$$ c^i=\prod_j P_j^{r_j} \leadsto i=\sum_j r_j \operatorname{ind}(P_j). $$請注意，由於 $ c^i $ 也會擊中 $ P_j $ ，我們有足夠的獨立方程來求解所有指數。當然，希望是我們不需要遍歷所有方程，但前幾個方程已經包含所有索引並且足夠線性獨立。c 的選擇對於一個人獲得足夠資訊來求解線性系統的速度很重要。
您可以將其推廣到更一般的群體，但想法保持不變。