Cryptanalysis
ECC 算法 pollard 的ρρrho複雜
破壞 ECDLP 的方法之一是 Pollard 的 rho 算法。當 ECDLP 在有限域上定義時 $ F_p $ , 並給定一個關係 $ S=w.T $ , 其中 S 和 T 是 $ F_p $ . 那麼ECDLP就是找w。
該算法應該需要一些時間 $ O(\sqrt p) $ .
作者說它充其量是指數或次指數。怎麼會這樣？
w 和 p 之間是否有任何關係使它成為指數？
維基文章說沒有任何引用：
該算法在其執行時間和它找到一個因素的機率之間提供了一個權衡。如果 n 是兩個不同的等長素數的乘積，則執行算法 $ O(n^{1/4} polylog(n)) $ 步驟產生一個機率大約為一半的因子。
$$ citation needed $$ （請注意，這是一個啟發式聲明，對算法的嚴格分析仍然開放。）
當我們說算法是“指數”或“多項式”時，意味著執行時間受輸入大小（以位為單位）的指數或多項式函式的限制。即函式的輸入不是 $ p $ ， 但 $ \log p $ . 所以， $ O(\sqrt p ) = O( e^{1/2 \log p}) $ 以指數為界 $ \log p $ .
另請注意，Wiki 文章不是在談論應用於 ECDLP 的 Pollard rho 算法，而是在談論應用於因式分解的 Pollard rho。對於應用於因式分解的 Pollard rho，所花費的時間是 $ p $ ， 在哪裡 $ p $ 是較小的因子；因此，（因為因子的長度大致相同） $ \sqrt p $ 大致是 $ n^{1/4} $ （與 $ polylog(n) $ 因為 Pollard rho 在這種情況下效率不高）。