在哪種情況下，數字域篩/索引演算求解離散對數更快？
給定正常的離散對數問題：
$$ a = b^c \mod{P} $$
帶素數 $ P $ 和數字 $ a,b,c $
對於哪一種 $ P,b $ NFS/IC 算法比 Baby-Step/Giant-Step+ Pollard 的 Rho ( $ \approx \mathcal{O}(\sqrt{q}) $ )?
（和 $ q $ 因式分解的最大素數 $ P-1 $ ， 和 $ P $ 大素數）
或者在哪些情況下它使用了 NFS/IC？
使用它的符號，問題是關於Schnorr 群模中離散對數問題的難度 $ P $ , 素數 $ q $ . 我會假設 $ b^q\bmod P=1 $ 和 $ b\bmod P\ne1 $ .
發現 DLP 問題 $ c $ 隨機選擇在 $ [0,q) $ 給定 $ P $ , $ q $ , $ b $ ， 和 $ a $ 獲得為 $ b^c\bmod P $ . 根據參數，最知名的算法分為兩個複雜度類別：
- 介於兩者之間 $ \mathcal O(\sqrt{q},\ln P,\ln\ln P) $
$$ in theory $$和 $ \mathcal O(\sqrt{q},\ln^2 P) $ 對於 Baby-Step/Giant-Step 及其實際改進：具有顯著點的 Pollard 的 Rho（可以有效地分佈並且需要很少的記憶體；參見 Paul C. van Oorschot 和 Michael J. Wiener，Parallel Collision Search with Cryptanalytic Applications，期刊密碼學，1999 年）。成本通常表示為 $ \mathcal O(\sqrt{q}) $ 大小整數的乘法 $ P $ ，而這最近被證明要花費 $ \mathcal O(\ln P,\ln\ln P) $ ，看這個。
- 就像是 $ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln P)^{\frac{1}{3}}(\ln \ln P)^{\frac{2}{3}}\right) $ ，對於應用於離散對數的數字域篩選器（請參閱此）。
在哪些情況下使用 NFS/索引演算？
對於給定的大小 $ q $ ，第一類算法（Pollard’s Rho..）最適合大型 $ P $ . 第二個（NFS）相對較小的速度更快 $ P $ ， 包含 $ q $ 一個Sophie Germain 素數（等價地， $ P $ 一個安全的素數）。
對於 256 位 $ q $ , 第一類算法對 8192-bit 更好 $ P $ , 第二個用於 512 位 $ P $ . 我不想探勘交叉點的確切位置，或者 NFS 和 IC 之間的確切區別是什麼。