愛德華茲曲線的階及其扭曲
在 Mike Hamburg 的Ed448-Goldilocks 中，一個新的橢圓曲線（eprint 2015，WECCS 2015）研究了素數域中的未扭曲 Edwards 曲線 $ \mathbb F_p $ $$ E_d:,y^2+x^2,=,1+d,x^2,y^2 $$ 大素數 $ p\equiv3\pmod 4 $ 和勒讓德符號 $ \displaystyle\left(\frac d p\right)=-1 $ .
匹配的“扭曲”是 $$ E’_d:,y^2-x^2,=,1-d,x^2,y^2 $$
持續的 $ d $ 選擇最小 $ |d| $ 使得曲線的順序 $ |E_d| $ 是 $ 4\cdot q $ 和 $ q $ 素數，扭曲的順序是 $ |E’_d|=4\cdot r $ 和 $ r $ 素數，和 $ q<p/4 $ .
論文使用素數 $ p=4^{224}-2^{224}-1 $ 並給出 $ d=-39081 $ ,
$ q=2^{446}-\mathtt{8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h} $ ,
$ r=2^{446}+\mathtt{0335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h} $
它擁有 $ |E_d|+|E’_d|=2\cdot p+2 $ . 更新：最初我的實驗¹有兩個不同，但 Mike Hamburg 指出我的錯誤：我沒有計算無窮大的兩個點 $ E’_d $ .
問題（現在）歸結為：為什麼 $ |E_d|+|E’_d|=2\cdot p+2 $ ? 以及我們如何找到 $ d $ 給定 $ p $ ?
如果後者僅僅是列舉 $ d\gets-j\cdot\displaystyle\left(\frac j p\right) $ 對於增量 $ j>0 $ 並檢查 $ q\gets|E_d|/4 $ 和 $ r\gets|E’_d|/4 $ 是素數，這些是如何計算的²？
¹ 有 $ p\gets4^i-2^i-1 $ 為了 $ i\in{4,5} $ ，我得到 $$ \begin{array}{r|rrr} i&p&d&q&r\ \hline 4&239&19&59&61\ 5&991&-45&233&263 \end{array} $$
² 這可能要求Schoof-Elkies-Atkin適應 Edwards 曲線。也歡迎指向實現的指針。
關於
$$ B $$和$$ C $$根據評論的部分問題： 我不確定 Mike Hamburg 究竟是如何找到曲線的，但據我所知，通常更容易找到匹配的蒙哥馬利曲線的順序。回想一下蒙哥馬利曲線的形式 $ By^2 = x^3 + Ax^2 + x $ . 如果 $ B $ 為 1，則它適合廣義 Weierstrass 形式，並且大多數 SEA 算法實現適用於廣義 Weierstrass 形式的任何曲線。（如果它不是 1 那麼你可以很容易地映射成一條曲線 $ B = 1 $ , 與短 Weierstrass 曲線可以映射到的方式相同 $ a = -3 $ )
所以基本上：
- 搜尋符合條件的蒙哥馬利曲線；
- 然後將其轉換為 Edwards 形式。
一種優化是指示 SEA 快速丟棄其預先知道的階數較小（4 或 8 除外）的曲線，例如，參見PARI/GP 函式的
tors參數ellsea。論文“關於高安全性通用橢圓曲線的說明”具有該過程的 Magma 實現（儘管 IIRC 它使用了稍微不同的方法）。RFC 7748有一個 Sage 腳本，它也搜尋蒙哥馬利曲線（儘管它可能會慢得多，因為它似乎不支持該優化）。