如何根據參數確定橢圓曲線組的階數？

讓 $ \quad E:; y^2 = x^3 + ax + b \quad $ 是在有限域上定義的橢圓曲線 $ \mathbb F_q $ 在哪裡 $ q = p^n $ , $ a,b \in \mathbb F_q $ 和 $ p \neq 2, 3 $ . 根據哈斯定理，我們知道 $ E(\mathbb F_q) $ 在範圍內 $ [q+1-2\sqrt{q}, q+1+2\sqrt{q}] $ .

是否可以確定順序 $ E(\mathbb F_q) $ 給定 $ a, b, q $ 不列舉要點？

有一個相當深的多項式時間算法來計算 $ \mathbb F_q $ - René Schoof於 1985 年發表的橢圓曲線的有理點（隨後由 Noam Elkies 和 AOL Atkin 進行了改進）。它基於兩個核心思想：

• 點數與函式方程密切相關 $$ \varphi^2-t\varphi+q = 0 \qquad\in\operatorname{End}(E) $$Frobenius 自同態 $$ \varphi\colon;E\to E,;\begin{cases}\mathcal O&\mapsto \mathcal O\(x,y)&\mapsto (x^q,y^q) \end{cases} $$ 滿足內同態環 $ E $ . 如果 $ t\in\mathbb Z $ 選擇使得這個方程成立，它被稱為*Frobenius 的跡，*可以證明 $$ #E(\mathbb F_q)=q+1-t \text. $$ （原因 $ \varphi $ 與點計數有任何關係是它準確地留下座標在 $ \mathbb F_q $ 不變的。）
• 對於奇數 $ l $ , 存在除法多項式 $ \psi_l\in\mathbb F_q $ 這恰好消失在 $ x $ - 有限的座標 $ l $ -扭力點 $ E $ . 因此，可以計算 $ t\bmod l $ 通過檢查哪個 $ k\in{0,\dots,l-1} $ 函式方程 $ \varphi^2-t\varphi+q=0 $ 保持模數 $ \psi_l $ . 計算模 $ \psi_l $ 大大提高了複雜度（與沒有任何減少的擴展項相比）。經過計算 $ t\bmod l $ 對於足夠大的（根據哈塞定理， $ \prod_{l\in L}l>4\sqrt q $ 就夠了）設置 $ L $ 奇素數，中國剩餘定理可以用來重構弗羅貝尼烏斯的踪跡 $ t $ ，從而產生的數量 $ \mathbb F_q $ -理性點 $ #E(\mathbb F_q) $ 上 $ E $ .

當然，在大多數電腦代數係統中都有這種算法（改進的變體）的實現。使用sage , 的數量 $ \mathbb F_{p^n} $ - 橢圓曲線的有理點 $$ y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6 $$ 定義在 $ \mathbb F_p $ 可以計算為：

EllipticCurve(GF(p), [a1, a2, a3, a4, a6]).cardinality(extension_degree = n)

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