計算二元體上橢圓曲線群之群秩：SEA演算法的實作

Abstract

目前尋找安全橢圓曲線的最好方法為群秩計算法 (Point-counting Method)。Schoof-Elkies-Atkin 演算法 (SEA 演算法) 為質數體上計算橢圓曲線群秩最有效率的演算法。Lercier 提出了計算二元體上同源的方法，使得 SEA 演算法也可應用基於二元體的橢圓取線上。這篇論文我們將依據 Lercier 提出的方法實作 SEA 演算法，用它來計算美國國家標準和技術研究院 (NIST) 推薦的十條曲線的群秩並觀察其效率。

The best suggested way to find secure elliptic curves is point-counting. So far Schoof-Elkies-Atkin algorithm (SEA algorithm) is the most efficient point-counting algorithm for elliptic curves over prime fields. Lercier proposed an algorithm to compute isogenies in GF(2^n) such that SEA algorithm can be used for binary case. In this thesis we will follow Lericier's approach to implement SEA algorithm computing the order of an elliptic curve over binary fields.