如何在橢圓曲線上應用 Pollard 的 Rho 方法來解決有限域中的離散對數問題？
我在有限域中實現了 ElGamal 簽名方案 $ \mathbb{F}_p $ . 問題是我需要在橢圓曲線上應用 Pollard 的 Rho 方法 $ E(\mathbb{F}_p) $ 對於這個方案，解決離散對數問題並找到私鑰 $ x $ . 在 ElGamal 計劃中，我有 $ a^x\equiv b\ (mod\ p) $ 在哪裡 $ a,\ b\in \mathbb{F}_p $ 在波拉德的 Rho 方法中，我有 $ Q=dP $ 在哪裡 $ P,Q\in E(\mathbb{F}_p) $ .
那麼我怎樣才能得到 $ P,\ Q $ 從 $ a,\ b $ 而且，在我得到之後 $ d $ ， 我怎樣才能得到 $ x $ 從中？
甚至有可能還是我完全錯了？
在你說的問題中 $ a^x\equiv b\ (mod\ p) $ 和 $ P,Q\in E(\mathbb{F}_p) $ . 一般情況下，橢圓曲線點數 $ #E(\mathbb{F}_p) $ 不等於 $ p $ . 所以這兩組不是同構的，你的問題是錯誤的。
如果 $ #E(\mathbb{F}_p)=p $ 該曲線稱為異常曲線，我們可以找到地圖 $ \psi : E(\mathbb{F}_p) \to \mathbb{Z}_p $ 在多項式時間內。在這種狀態下， $ a=\psi(P),b=\psi(Q) $ 和 $ x=d $ .
Pollard 的 rho 算法背後的主要思想是找到不同的對 $ (c’ , d’ ) $ 和 $ (c’’ , d’’ ) $ 整數模 $ n $ 這樣 $ c’ P + d’ Q = c’’ P + d’’ Q $ . 所以 $ (c’ − c’’ ) = (d’’ − d’ )d \pmod n $ . 因此 $ d $ 可以通過計算得到
$$ d = (c’ − c’’ )(d’’ − d’ )^{ −1} \pmod n. $$ 有關更多詳細資訊，您可以查看頁面 $ 156,168 $ “橢圓曲線密碼學指南”，漢克森，….