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

プライバシーポリシー

お問い合わせ

スポンサーリンク