是否僅出於性能原因使用輔因子來查找基點？

對於橢圓曲線密碼學，尋找基點以生成具有順序的子群的過程 $ n $ 是：

1. 計算順序 $ N $ 橢圓曲線的（使用 Schoof 的）
2. 選擇 $ n $ . $ n $ 必須是素數並且是的除數 $ N $
3. 計算輔因子 $ h = \frac{N}{n} $
4. 選擇一個隨機點 $ P $ 在曲線上
5. 計算 $ G = hP $
6. 如果 $ G $ 為0，則返回第4步。否則，您找到了一個有順序的生成器 $ n $ 和輔因子 $ h $

資源

輔助因子的目的僅僅是為了提高尋找大型子組的效率嗎？

我想如果你不使用協因子而是嘗試蠻力計算隨機點是否， $ P $ , 是一個大小子組的生成器 $ n $ 你必須做 $ n $ 迭代，這在現代電腦上是不可能的。但是，我想確認一下。

**編輯：**我的最後一段是錯誤的 b/c 我們可以使用重複平方來計算 $ G = nP $

輔助因子的目的僅僅是為了提高尋找大型子組的效率嗎？

好吧，這個替代算法可以工作（假設 $ n $ 是素數；實際上，兩種算法都假設 $ n $ 是素數）：

4. 在曲線上選擇一個隨機點 P（除了無窮遠處的點）
5. 計算 $ G = nP $
6. 如果 $ G \ne 0 $ , 回到第 4 步。否則，你找到了一個有順序的生成器 $ n $ 和輔因子 $ h $

該算法將起作用；然而，它顯然效率低得多；部分原因是計算 $ nP $ 將比計算貴得多 $ hP $ （我們通常有 $ n \ggg h $ )，並且在修改後的版本中，您將獲得預期的 $ h $ 在找到點之前進行迭代，而在原始算法中，這是預期的 $ 1 + 1/n $ 迭代（也就是說，最後的測試幾乎永遠不會失敗）。

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