Pebble Coding

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

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

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

の続きです。

 a \mod l = cを素数 l=2, 3, 5, ...について計算するアルゴリズムは以下の通りです。

素体 F_q, 楕円曲線 x^{3} + Ax + B = y^{2}とします。
まず、l=2の場合は、 gcd(x^{3} + Ax + B, x^{q} - x)の値が1かどうか調べます。
ここでgcdはxの素体 F_q上の1変数多項式での最大公約数を意味します。
値が1の場合は  a = 1 \mod 2、1でない場合は a = 0 \mod 2となり完了です。
残りはl=3以上の場合です。

a)  q_l = q \mod l, |q_l| \lt l / 2を求めます。

b)  j = 1, 2, ..., (l-1)/2に対して以下を実行します。

b-i) (x, y) のj等倍点のx, yの2変数多項式を計算し、 (x_j, y_j)とします。
ここではまだ x_jだけ計算すればよく、 y_jはあとでもよいです。
j等倍点の多項式の具体的な表現は複雑なのでここでは省略し次の記事に回します。

b-ii)  (x', y') = (x^{q^{2}}, y^{q^{2}}) + q_l (x, y) \mod \psi_l(x)のx'を計算します。
 \psi_l(x)というのは除法多項式(division polynomial)と呼ばれるx, yの2変数多項式で、
楕円曲線の係数A, Bから一意的に決まるものですが、具体的な表現は複雑なので省略し次の記事に回します。
係数が奇数の場合はxのみの多項式となりますがlは奇素数なので、xの多項式です。
真ん中のプラスは楕円曲線の2点の加法を表します。
ここでの2点は等しくないと仮定してよいです。
2点が等しい場合は、d)以降のロジックでカバーするようになっています。
\mod \psi_l(x, y)というのは、 F_q上のx, yの2変数多項式でのモジュラ演算を意味します。
 q_l (x, y)は点(x, y)を q_l倍した点という意味です。
2変数多項式であるx'を計算したら、
 x' = x_j^{q} \mod \psi_l(x, y)が成り立つかどうか調べます。
成り立つ場合はb-iii)へ進みます。成り立たない場合は、次のjに対してb-i)を行います。
全てのjに対して成り立たない場合はd)へ進みます。

b-iii) y'と y_jを計算します。どちらも、yが係数につくことがわかっていますので、
 y'/y = y_j^{q}/y \mod \psi_l(x, y)が成り立つか調べます。
成り立つ場合は a = j \mod l、成り立たない場合は a = -j \mod lで完了です。

d)  w^{2} = q \mod lを満たすwが存在するか計算します。
存在しない場合は a = 0 \mod lとなり完了です。
存在する場合はe)へ進みます。

e) w等分点のx座標を求めます。 gcd(numerator({x}^{q}-x_w), \psi_l(x, y)) が1かどうか調べます。
1の場合は、 a = 0 \mod lで完了です。
1でない場合は、 gcd(numerator( ( {y}^{q} - y_w) / y), \psi_l(x, y)) を計算します。
1の場合は、 a = -2w \mod lで完了、
1でない場合は、 a = 2w \mod lで完了です。

素体上の多項式の計算が山ほど出てきて、手計算でやるにはしんどいですね。
実際には、プログラミング言語やsageなど多項式を扱えるシステムを使うことになります。

schoofのアルゴリズムはベビーステップジャイアントステップ法よりも効率がよいことが知られています。

現在、暗号に利用されている170bitを超える素体上の楕円曲線の位数はSchoof法を改良したSchoof-Elkies-Atkinsで計算されているようです。

http://memoirs.is.kochi-u.ac.jp/Vol28/MemoirsF28-1.pdf

補足

 x^{3} + A x + B = 0が根 e \in F_qを持つとすると、 e^{3} + A e + B = 0を満たすeがあり、 点P(e, 0)が曲線上の点になり、P+P = Oです。
P + P = 0つまり2P = Oなので、2倍点です。
この2倍点が存在するので、Oと合わせて、{P, O}が位数2の部分群をなすことになります。
ラグランジュの定理により楕円曲線の有理点の個数#Eは部分群の位数の倍数になるので、#Eは2の倍数だと分かります。
#E=q+1-aで#Eが偶数、qは奇数なのでaは偶数と確定します。

有限体の理論より、 x^{q} - x = 0を満たすxは F_qの要素なので、
 x^{3} + A x + B=0 F_qで根を持つとき、 x^{q} - x = 0の根でもあります。
したがって、 x^{q} - x x^{3} + A x + Bで割り切れるとき、 x^{3} + A x + B = 0 F_qに根を持ちます。
なので、 gcd(x^{q} - x, x^{3} + A x + B)=1かどうかを調べればよいことが分かります。