如何在橢圓曲線上找到生成器的階數？

我一直在尋找橢圓曲線的最佳生成器 $ E $ 在素數場上 $ \mathbb F_p $ . 我發現了以下算法：

1. 選擇隨機點 $ P $ 曲線上。
2. 查找生成器的順序 $ \ell $ .
3. 計算點數 $ n=#E(\mathbb F_p) $ .
4. 計算輔因子 $ h=n/\ell $ .
5. 計算生成器為 $ G=[h]P $ .

在這裡我可以找到 $ n=#E(\mathbb F_p) $ 使用 Schoof 算法。我需要找到 $ \ell $ . 這怎麼可能？如何找到在素數域上定義的橢圓曲線的生成器/基點的階數？

由於Pohlig-Hellman 算法，離散對數的硬度由最大的素因子控制 $ \ell $ 組序的 $ n $ . 特別是，一個人通常在一個子組中工作 $ \ell $ 曲線組的，因為附加因素 $ h $ 按照發電機的順序不會顯著提高安全性。

其中，請注意 $ \ell $ 取決於組順序 $ n $ : 你不能只決定某個訂單 $ \ell $ 然後找一個點 $ G $ 在任意固定曲線上具有該順序，因為通常不會存在這樣的點。（但是，有復數乘法方法，它會生成給定順序的新曲線。） 因此，問題中給出的算法的步驟 2 和 3 必須交換：您首先計算曲線組順序 $ n $ , 分解它, 並確定 $ \ell $ 從因式分解。（而如果 $ \ell $ 太小，您應該從新曲線重新開始。例如，Curve25519 有輔因子 $ h=8 $ .)

除此之外，算法很好，除了你可能想檢查是否 $ G=\infty $ 並在這種情況下重新開始。然而，這只會發生在機率上 $ 1/\ell $ ，所以它在實踐中不應該發生在加密大小的曲線上。（此外，您只需計算和分解一次組順序並找到一個好的 $ P $ 之後，但這不會影響預期的執行時間 $ P $ 通常在第一次嘗試時很擅長。）

因此，我們有以下算法：

1. 計算曲線階 $ n=#E(\mathbb F_p) $ .
2. 因素 $ n $ 確定其最大的主要因素 $ \ell $ . （請注意，您不需要完全考慮 $ n $ ：如果去掉一些“小”除數後的餘數不是素數，那麼輔因子無論如何都會太大。）
3. 計算輔因子 $ h=n/\ell $ . 如果 $ h $ 是“太大”，從新曲線重新開始。
4. 選擇一個隨機點 $ P\in E(\mathbb F_p) $ 然後讓 $ G=[h]P $ .
5. 如果 $ G $ 是無窮大的點，回去選擇一個新的 $ P $ . 別的， $ G $ 有訂單 $ \ell $ .

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