Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

Schoofアルゴリズム

SEAアルゴリズムで使う漸化式を導く

Elliptic Curves in Cryptography の VII.23の等式から、VII.24の漸化式を導く計算 証明すべき等式は以下です。 ここからVII.24が得られます。 使う材料は以下です。 (式A) 最初の等式の両辺のwの0乗からd乗までの多項式を計算し、係数を等しいと置くことが…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその5

schoofアルゴリズムをpythonで実装したらめちゃくちゃ遅かったのですが、楕円曲線の有理点の数の求め方 schoof アルゴリズムその4 - Pebble Codingrustで実装したところ、 a = -1 mod 3 a = -2 mod 5 の計算が、Debugビルドで90秒、Releaseビルドで7秒で計…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその4

y'についてもみていきます。 を使うと、 残りのフロベニウス写像部分は したがって、 分母を揃え、分子だけ取り出したものがで割り切れるかどうかを調べます。 コンピュータ計算上は分母にyが含まれるか否かの分岐が面倒なので、 分子だけの計算結果にyが含…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその3

アルゴリズムの実際の計算をもう少し詳しくみていきます。 が成り立つかどうかの計算をみていきます。 まず、この式はがreductionの最終結果がxのみの多項式で分母と分子があるということを意味します。 lは奇数なのでにはyは入らないです。 そして、で割り…

楕円曲線の有理点の数の求め方 schoof アルゴリズムその2

楕円曲線の有理点の数の求め方 schoof アルゴリズムその1 - Pebble Coding の続きです。 を素数 l=2, 3, 5, ...について計算するアルゴリズムは以下の通りです。 素体, 楕円曲線とします。 まず、l=2の場合は、の値が1かどうか調べます。 ここでgcdはxの素…