求解ECDLP的小複數乘法域判別法
我從SafeCurve標準中看到，應該盡量避免小的複數乘法域判別，因為它可以通過 Polard Rho 方法加速離散對數計算。
但是，我找不到有關此附加資訊如何改進 rho 方法的任何資訊。特別是，SafeCurve 頁面似乎很模糊，提到我們不確定一個小的判別式（甚至非常小的判別式，例如 3）是否會導致災難性後果。有人可以解釋一下這種特殊結構如何（在某些情況下）改進 rho 方法嗎？
在回答你的問題之前，我首先回顧一下離散對數問題和 Pollardrho 算法的一些基礎知識*。*
離散對數問題
給定一個點 $ P $ 素數的 $ q $ 在橢圓曲線上，並且 $ Q $ 生成的子組中的一個點 $ P $ , 那麼存在 $ k $ 這樣 $ Q = kP $ 在哪裡 $ 0\leq k < q $ .
的離散對數 $ Q $ 在基地 $ P $ 是 $ k $ ，並且離散對數問題正在尋找 $ k $ 會心 $ P $ 和 $ Q $
Pollard- rho算法
Pollard- rho算法關於素數的一般群 $ q $ 複雜度為 $ \sqrt{\pi q/2} $ .
它的原理是通過pose來構造一個點序列 $ R_0 = a_0P+b_0Q $ 隨機整數 $ a_0 $ 和 $ b_0 $ ，然後使用函式 $ f $ 充當偽隨機遊走以獲得點序列： $$ R_{i+1} = f(R_i) = a_{i+1} P + b_{i+1} Q. $$ 最終會有一點 $ R_j $ 等於前一點 $ R_i $ 在序列中。然後，我們推斷： $$ k \equiv (a_i - a_j)(b_j-b_i)^{-1} \mod q, $$ 如果，當然， $ (b_j-b_i) $ 是可逆的（但這很有可能是這種情況）。
現在，生日悖論給出了上述複雜性。
加速rho
在橢圓曲線上，很容易計算 $ -P $ 從 $ P=(x,y) $ 自從 $ -P=(x,-y) $ . 然後，我們可以成對地重新組合曲線的所有點 $ {P,-P} $ .
而不是尋找點之間的碰撞 $ R_i $ 和 $ R_j $ 在序列中，我們尋找他們的碰撞 $ x $ -協調。如果我們有，將找到離散對數 $ R_i = \pm R_j $ .
就好像沒有對所有點進行搜尋，而只是對其中一半進行了搜尋。那麼值 $ q $ 在復雜性被替換為 $ q/2 $ ，這給出了複雜度 $ \sqrt{q\pi/4} $ （您可以在 SafeCurves 網站上找到相應的頁面）。
進一步加速rho
我們上面所做的事情是可能的，因為我們有地圖（稱為內同態） $ [-1] $ : $$ \begin{array}{rrcl} [-1]: & E & \longrightarrow & E \ & (x,y) & \longmapsto & (x,-y) \end{array} $$ 發送橢圓曲線的一個點 $ E $ 到它的對面。我們可以看到，如果我們應用它兩次，我們就回到了原來的點。我們說這張地圖有秩序 $ 2 $ ，這就是我們可以成對分組的原因。而且很容易計算。
現在的問題是：是否存在其他易於計算的此類映射，可用於大幅加速rho？
答案是肯定的。例如，曲線
secp256k1具有以下自同態： $$ \begin{array}{rrcl} \phi: & \texttt{secp256k1} & \longrightarrow & \texttt{secp256k1} \ & (x,y) & \longmapsto & (\beta x,y) \end{array} $$ 在哪裡 $ \beta $ 是秩序的一個要素 $ 3 $ （滿足 $ \beta^3=1 $ 和 $ \beta \neq 1 $ ) 在曲線的有限域中。然後我們有： $$ (x,y) \mapsto (\beta x, y) \mapsto (\beta^2 x, y) \mapsto (\beta^3 x, y) = (x,y), $$ 這意味著 $ \phi $ 是 $ 3 $ .然後我們可以將曲線的點按三個一組進行分組： $ { P, \phi(P), \phi^2(P)} $ . 我們選擇三個點之一作為代表（例如最小的點 $ x $ -座標被視為一個整數）。而不是在 Pollardrho 中搜尋碰撞 $ q $ 點，我們搜尋碰撞 $ q/3 $ 代表。由此，我們推斷在這條曲線上我們可以除以一個因子 $ \sqrt 3 $ Pollardrho 的複雜性。結合之前的加速，這給出了一個複雜度 $ \sqrt{q\pi/12} $ .
與 CM 場判別式的關係
關鍵是我們想要一個易於計算的內同態，否則加速 Pollardrho 將沒有用處。正如我們所看到的，上面給出的這兩個例子非常簡單。因為他們的學位是 $ 1 $ ，這意味著計算座標的有理函式 $ \phi(P) $ 是多項式 $ 1 $ .
CM-field 判別式與小度內同態的存在有關係。在曲線的情況下
secp256k1，這個判別式是 $ -3 $ 與內同態直接相關 $ \phi $ 用這個公式： $$ \left(\frac{1+i\sqrt 3}{2}\right)\left(\frac{1 - i\sqrt 3}{2}\right) = 1, $$ 這意味著存在一個非平凡的度數自同態 $ 1 $ ，也就是上面給出的那個。我希望我提供了一些元素來回答你的問題。稍後我將嘗試擴展和糾正一些觀點。