我想使用Pohlig-Hellman並BSGS解決具有復合訂單生成器的橢圓曲線的離散對數。

棘手的部分是，複合因子組之一很大（99 位），所以我想將它從Pohlig-Hellman/BSGS.

是否可以SageMath將該discrete_log()函式應用於橢圓曲線，並排除其中一個生成因子？

有訣竅Chinese remainder theorem嗎？

假設我們有一個觀點 $ P $ 有秩序的 $ q $ 在橢圓曲線上，其中的素數分解 $ q $ 是 $ q = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n} $ . 我們也有一點 $ Q=kP $ 我們想找到 $ k $ .

Pohlig-Hellman 算法

Pohlig-Hellman 算法的思想是計算素數子群中的離散對數。

簡易案例

我們假設 $ \alpha_i=1 $ 為了 $ 1\leq i \leq n $ ， 所以 $ q=p_1\cdots p_n $ 並且所有素數都是不同的。

讓 $$ \begin{align} q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j} \ P_i & = q_i P, \ Q_i & = q_i Q. \end{align} $$

重點 $ P_i $ 有訂單 $ p_i $ 我們有 $ Q_i = k_i P_i $ 在哪裡 $ k_i = k \bmod p_i $ . 離散對數可以用discrete_logSage 或其他軟體計算，值 $ k_i $ 被恢復。

僅對您感興趣的素數執行此操作，例如足夠小的素數。如果值 $ k $ 次於這些素數的乘積，將使用中國剩餘定理 ( CRT([list of k_i], [list of p_i]).

硬殼

現在我們假設 $ \alpha_i $ 大於 $ 1 $ 對於他們中的一些人。同樣，我們計算 $$ \begin{align} q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j^{\alpha_j}} \ P_i & = q_i P, \ Q_i & = q_i Q. \end{align} $$ 重點 $ P_i $ 有訂單 $ p_i^{\alpha_i} $ 我們有 $ Q_i = k_i P_i $ 在哪裡 $ k_i = k \bmod p_i^{\alpha_i} $ . 然後，我們寫出分解 $ k_i $ 在基地 $ p_i $ : $$ k_i = k_{i,0} + k_{i,1}p_i + k_{i,2}p_i^2 + \cdots + k_{i,\alpha_i-1}p_i^{\alpha_i-1}, $$ 在哪裡 $ 0 \leq k_{i,j} < p_i $ 為了 $ 0 \leq j < \alpha_i $ . 獲得 $ k_i $ ，我們將得到所有 $ k_{i,j} $ 逐個。首先，對於 $ k_{i,0} $ ，我們構造以下兩點： $$ \begin{align} P_{i,0} & = p_i^{\alpha_i-1} P_i, \ Q_{i,0} & = p_i^{\alpha_i-1} P_i. \end{align} $$ 重點 $ P_{i,0} $ 是一個程序問題 $ p_i $ 我們有關係 $ Q_{i,0} = k_{i,0} P_{i,0} $ . 離散對數可以用 計算discrete_log。

下一個值 $ k_{i,1} $ 可以通過類似的方式找到。我們計算 $$ Q_{i,1} = p_i^{\alpha_i-2} (Q_i-k_{i,0}P_i) $$ 我們有 $ Q_{i,1} = k_{i,1}P_{i,0} $ , 並discrete_log給出值 $ k_{i,1} $ . 然後 $$ Q_{i,2} = p_i^{\alpha_i-3} (Q_i-(k_{i,0}+k_{i,1}p_i)P_i)), $$ 我們有 $ Q_{i,2} = k_{i,2}P_{i,0} $ ，我們得到 $ k_{i,2} $ ，以此類推，直到 $ k_i $ 已經完成。

同樣，僅對素數執行此操作 $ p_i $ 這符合您的利益。

引用自：https://crypto.stackexchange.com/questions/80219