Efficient algorithm to count points on elliptic curves
シューフのアルゴリズムは、 有限体 上の 楕円曲線 上の点を数える効率的なアルゴリズムです 。このアルゴリズムは、 楕円曲線上の点 群 における 離散対数問題 を解く難易度を判断するために点の数を知ることが重要となる 楕円曲線暗号に応用されています。
このアルゴリズムは1985年に ルネ・シューフによって発表され、 楕円曲線上の点を数える 最初の決定論的多項式時間アルゴリズムとして理論上のブレークスルーとなりました。シューフのアルゴリズム以前は、楕円曲線上の点を数えるナイーブアルゴリズムや ベイビーステップ・ジャイアントステップ アルゴリズムといったアプローチは 、ほとんどの場合、面倒で実行時間が指数関数的でした。
この記事では、アルゴリズムの構造の基礎となる数学的な考え方に重点を置いて、Schoof のアプローチについて説明します。
導入 を有限体 上で定義された 楕円曲線 とする 。 ここで 、 は 素数、 は 整数で ある。特性体 上の 楕円曲線は、（短縮）ワイエルシュトラス方程式で与えられる。 E {\displaystyle E} F q {\displaystyle \mathbb {F} _{q}} q = p n {\displaystyle q=p^{n}} p {\displaystyle p} n {\displaystyle n} ≥ 1 {\displaystyle \geq 1} ≠ 2 , 3 {\displaystyle \neq 2,3}
y 2 = x 3 + A x + B {\displaystyle y^{2}=x^{3}+Ax+B} を満たす 。上で定義される点の集合は、 曲線方程式を満たす 解と 無限遠点 から構成される。この集合に制限された楕円曲線上の 群法則を用いると、この集合は アーベル群 を形成し 、 は零元として作用すること がわかる 。楕円曲線上の点を数えるには、 の濃度を計算する 。Schoofによる濃度計算のアプローチでは、 楕円曲線上のハッセの定理 に加え、 中国剰余定理 と 除算多項式 も利用している 。 A , B ∈ F q {\displaystyle A,B\in \mathbb {F} _{q}} F q {\displaystyle \mathbb {F} _{q}} ( a , b ) ∈ F q 2 {\displaystyle (a,b)\in \mathbb {F} _{q}^{2}} O {\displaystyle O} E ( F q ) {\displaystyle E(\mathbb {F} _{q})} O {\displaystyle O} E ( F q ) {\displaystyle E(\mathbb {F} _{q})} # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})}
ハッセの定理 ハッセの定理は、 有限体 上の楕円曲線 が 次の式 を満たすこと
を述べている。 E / F q {\displaystyle E/\mathbb {F} _{q}} F q {\displaystyle \mathbb {F} _{q}} # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})}
∣ q + 1 − # E ( F q ) ∣≤ 2 q . {\displaystyle \mid q+1-\#E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.} 1934年にハッセによって示されたこの強力な結果は、 可能性の有限集合（ただし大規模）に絞り込むことで、我々の問題を単純化します。 を と定義し 、この結果を利用すると、 を法として の値を計算することで を決定でき、したがって を決定できることがわかります 。 一般 的 な を直接 計算する効率的な方法はありませんが、 小さな素数 を 計算することは比較的効率的に可能です。 となる異なる素数の集合 を選びます 。 すべての についてが与えられている場合 、 中国剰余定理 により を計算できます 。 # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})} t {\displaystyle t} q + 1 − # E ( F q ) {\displaystyle q+1-\#E(\mathbb {F} _{q})} t {\displaystyle t} N {\displaystyle N} N > 4 q {\displaystyle N>4{\sqrt {q}}} t {\displaystyle t} # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})} t ( mod N ) {\displaystyle t{\pmod {N}}} N {\displaystyle N} t ( mod l ) {\displaystyle t{\pmod {l}}} l {\displaystyle l} S = { l 1 , l 2 , . . . , l r } {\displaystyle S=\{l_{1},l_{2},...,l_{r}\}} ∏ l i = N > 4 q {\displaystyle \prod l_{i}=N>4{\sqrt {q}}} t ( mod l i ) {\displaystyle t{\pmod {l_{i}}}} l i ∈ S {\displaystyle l_{i}\in S} t ( mod N ) {\displaystyle t{\pmod {N}}}
素数 を 計算するには、フロベニウス準同型性 と 除法多項式 の理論を利用します 。素数を考慮することは、積が十分に大きくなるように、常により大きな素数を選ぶことができるため、何ら損失にはならないことに注意してください。いずれにせよ、小さな標数体には より効率的な、いわゆる進アルゴリズムが存在するため、 Schoofのアルゴリズムは、このようなケースに対処する際に最も頻繁に使用されます 。 t ( mod l ) {\displaystyle t{\pmod {l}}} l ≠ p {\displaystyle l\neq p} ϕ {\displaystyle \phi } l ≠ p {\displaystyle l\neq p} q = p {\displaystyle q=p} p {\displaystyle p}
フロベニウス準同型 上で定義された 楕円曲線が与えられたとき、 上 の点 、すなわち の 代数閉包を 考えます。つまり、 内の座標を持つ点を許します 。 上の の フロベニウス自己準同型は 、 によって楕円曲線に拡張されます 。 E {\displaystyle E} F q {\displaystyle \mathbb {F} _{q}} E {\displaystyle E} F ¯ q {\displaystyle {\bar {\mathbb {F} }}_{q}} F q {\displaystyle \mathbb {F} _{q}} F ¯ q {\displaystyle {\bar {\mathbb {F} }}_{q}} F ¯ q {\displaystyle {\bar {\mathbb {F} }}_{q}} F q {\displaystyle \mathbb {F} _{q}} ϕ : ( x , y ) ↦ ( x q , y q ) {\displaystyle \phi :(x,y)\mapsto (x^{q},y^{q})}
この写像は 上の恒等写像であり 、これを無限遠点 まで拡張して から自身へ の 群写像 にすることができます 。 E ( F q ) {\displaystyle E(\mathbb {F} _{q})} O {\displaystyle O} E ( F ¯ q ) {\displaystyle E({\bar {\mathbb {F} }}_{q})}
フロベニウス自己準同型は、 次の定理によって の基数に関連付けられた二次多項式を満たします。 E ( F q ) {\displaystyle E(\mathbb {F} _{q})}
定理： によって与えられるフロベニウス準同型は、 特性方程式を満たす。 ϕ {\displaystyle \phi }
ϕ 2 − t ϕ + q = 0 , {\displaystyle \phi ^{2}-t\phi +q=0,} どこ t = q + 1 − # E ( F q ) {\displaystyle t=q+1-\#E(\mathbb {F} _{q})} したがって、 に対して が成り立ちます。 ここ で、 + は楕円曲線上の加算を表し、 および は に よるのスカラー乗算 、による のスカラー乗算を表します 。 P = ( x , y ) ∈ E {\displaystyle P=(x,y)\in E} ( x q 2 , y q 2 ) + q ( x , y ) = t ( x q , y q ) {\displaystyle (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})} q ( x , y ) {\displaystyle q(x,y)} t ( x q , y q ) {\displaystyle t(x^{q},y^{q})} ( x , y ) {\displaystyle (x,y)} q {\displaystyle q} ( x q , y q ) {\displaystyle (x^{q},y^{q})} t {\displaystyle t}
これらの点、 、 を の 座標環上 の関数として 記号的に計算し 、方程式を満たす の値を探すという方法もあります 。しかし、次数が非常に大きくなるため、この方法は現実的ではありません。 ( x q 2 , y q 2 ) {\displaystyle (x^{q^{2}},y^{q^{2}})} ( x q , y q ) {\displaystyle (x^{q},y^{q})} q ( x , y ) {\displaystyle q(x,y)} F q [ x , y ] / ( y 2 − x 3 − A x − B ) {\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)} E {\displaystyle E} t {\displaystyle t}
シューフのアイデアは、この計算を様々な小さな素数 の 位数点に限定して実行するというものでした 。奇数の素数を固定し、 与えられた素数 に対して （ と定義される） を決定する問題を解くことに移ります 。点が - 捩れ部分群 に属する場合 、が かつ と なる唯一の整数 は です 。また、任意の整数に対して が成り立つことに注意してください 。したがって、 は と 同じ位数を持ちます 。したがって 、 に属する に対して が成り立つ 場合も が成り立ちます 。したがって、問題は次の方程式を解くことに帰着します。 l {\displaystyle l} l {\displaystyle l} l {\displaystyle l} t l {\displaystyle t_{l}} t ( mod l ) {\displaystyle t{\pmod {l}}} l ≠ 2 , p {\displaystyle l\neq 2,p} ( x , y ) {\displaystyle (x,y)} l {\displaystyle l} E [ l ] = { P ∈ E ( F q ¯ ) ∣ l P = O } {\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}} q P = q ¯ P {\displaystyle qP={\bar {q}}P} q ¯ {\displaystyle {\bar {q}}} q ≡ q ¯ ( mod l ) {\displaystyle q\equiv {\bar {q}}{\pmod {l}}} ∣ q ¯ ∣< l / 2 {\displaystyle \mid {\bar {q}}\mid <l/2} ϕ ( O ) = O {\displaystyle \phi (O)=O} r {\displaystyle r} r ϕ ( P ) = ϕ ( r P ) {\displaystyle r\phi (P)=\phi (rP)} ϕ ( P ) {\displaystyle \phi (P)} P {\displaystyle P} ( x , y ) {\displaystyle (x,y)} E [ l ] {\displaystyle E[l]} t ( x q , y q ) = t ¯ ( x q , y q ) {\displaystyle t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})} t ≡ t ¯ ( mod l ) {\displaystyle t\equiv {\bar {t}}{\pmod {l}}}
( x q 2 , y q 2 ) + q ¯ ( x , y ) ≡ t ¯ ( x q , y q ) , {\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q}),} ここで 、 および は整数値を持ちます 。 t ¯ {\displaystyle {\bar {t}}} q ¯ {\displaystyle {\bar {q}}} [ − ( l − 1 ) / 2 , ( l − 1 ) / 2 ] {\displaystyle [-(l-1)/2,(l-1)/2]}
素数を法とする計算 l 次 多項式は、その根が l 位の点の x座標 と 正確に一致するような式です 。したがって、 の計算を l 次ねじれ点に限定すること は 、これらの式を E の座標環上の関数として 、 かつ l 次多項式を法として計算することを意味します。つまり、 において作業していることになります。これは特に、 によって定義される X と Y の次数が、 y において最大で 1 、 x において 最大で であることを意味します 。 ( x q 2 , y q 2 ) + q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)} F q [ x , y ] / ( y 2 − x 3 − A x − B , ψ l ) {\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})} ( X ( x , y ) , Y ( x , y ) ) := ( x q 2 , y q 2 ) + q ¯ ( x , y ) {\displaystyle (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)} ( l 2 − 3 ) / 2 {\displaystyle (l^{2}-3)/2}
スカラー乗算は、 倍精度加算 法またはth 除算多項式 のいずれかで行うことができます 。後者の方法では以下のようになります。 q ¯ ( x , y ) {\displaystyle {\bar {q}}(x,y)} q ¯ {\displaystyle {\bar {q}}}
q ¯ ( x , y ) = ( x q ¯ , y q ¯ ) = ( x − ψ q ¯ − 1 ψ q ¯ + 1 ψ q ¯ 2 , ψ 2 q ¯ 2 ψ q ¯ 4 ) {\displaystyle {\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{\bar {q}}-1}\psi _{{\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\right)} ここで は n 次除算多項式です。
は x のみの関数であり 、 と表記されることに注意してください 。 ψ n {\displaystyle \psi _{n}} y q ¯ / y {\displaystyle y_{\bar {q}}/y} θ ( x ) {\displaystyle \theta (x)}
問題を の場合 と の場合 の2つのケースに分割する必要があります。 これらの等式は を法として検証されることに注意してください 。 ( x q 2 , y q 2 ) ≠ ± q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)} ( x q 2 , y q 2 ) = ± q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)} ψ l {\displaystyle \psi _{l}}
ケース1: ( x q 2 , y q 2 ) ≠ ± q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)} グループの 加法式 を使用すると 次のようになります。 E ( F q ) {\displaystyle E(\mathbb {F} _{q})}
X ( x , y ) = ( y q 2 − y q ¯ x q 2 − x q ¯ ) 2 − x q 2 − x q ¯ . {\displaystyle X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}-x^{q^{2}}-x_{\bar {q}}.} 不等式の仮定が間違っていた場合、この計算は失敗することに注意してください。
x 座標を用いて、選択肢を正の場合と負の場合の2つの可能性に絞り込むこと ができます 。その後、 y 座標を用いて、どちらの場合が成立するかを判断します。 t ¯ {\displaystyle {\bar {t}}}
まず、 Xが x 単独の関数であることを示します 。 を考えてみましょう 。は偶数なので、 を に 置き換えると 、式は次のように書き直されます。 ( y q 2 − y q ¯ ) 2 = y 2 ( y q 2 − 1 − y q ¯ / y ) 2 {\displaystyle (y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{2}} q 2 − 1 {\displaystyle q^{2}-1} y 2 {\displaystyle y^{2}} x 3 + A x + B {\displaystyle x^{3}+Ax+B}
( x 3 + A x + B ) ( ( x 3 + A x + B ) q 2 − 1 2 − θ ( x ) ) 2 {\displaystyle (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))^{2}} そしてそれを持っている
X ( x ) ≡ ( x 3 + A x + B ) ( ( x 3 + A x + B ) q 2 − 1 2 − θ ( x ) x q 2 − x q ¯ ) 2 mod ψ l ( x ) . {\displaystyle X(x)\equiv (x^{3}+Ax+B)\left({\frac {(x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}{\bmod {\psi }}_{l}(x).} さて 、 ある に対して が 成り立つ
とすると、 は X ≡ x t ¯ q mod ψ l ( x ) {\displaystyle X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)} t ¯ ∈ [ 0 , ( l − 1 ) / 2 ] {\displaystyle {\bar {t}}\in [0,(l-1)/2]} t ¯ {\displaystyle {\bar {t}}}
ϕ 2 ( P ) ∓ t ¯ ϕ ( P ) + q ¯ P = O {\displaystyle \phi ^{2}(P)\mp {\bar {t}}\phi (P)+{\bar {q}}P=O} すべてのl ねじれ点 P について 。
前述のように、 Y と を用いることで、 （ または） のどちらの値が 機能するかを判断できます。これにより の値が得られます。Schoofのアルゴリズムは、対象となる素数 l ごとに の値を 変数に格納します 。 y t ¯ q {\displaystyle y_{\bar {t}}^{q}} t ¯ {\displaystyle {\bar {t}}} t ¯ {\displaystyle {\bar {t}}} − t ¯ {\displaystyle -{\bar {t}}} t ≡ t ¯ ( mod l ) {\displaystyle t\equiv {\bar {t}}{\pmod {l}}} t ¯ ( mod l ) {\displaystyle {\bar {t}}{\pmod {l}}} t l {\displaystyle t_{l}}
ケース2: ( x q 2 , y q 2 ) = ± q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)} まず、 という仮定から始めます 。l は奇数の素数なので 、 にはなり得ず 、したがって となります 。特性方程式から が成り立ちます 。したがって となります 。これは、 q が l を法とする平方数であることを意味します 。 とします 。 を計算し 、 かどうかを確認します 。 そうであれば、 は y 座標に依存します。 ( x q 2 , y q 2 ) = q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)} q ¯ ( x , y ) = − q ¯ ( x , y ) {\displaystyle {\bar {q}}(x,y)=-{\bar {q}}(x,y)} t ¯ ≠ 0 {\displaystyle {\bar {t}}\neq 0} t ¯ ϕ ( P ) = 2 q ¯ P {\displaystyle {\bar {t}}\phi (P)=2{\bar {q}}P} t ¯ 2 q ¯ ≡ ( 2 q ) 2 ( mod l ) {\displaystyle {\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}} q ≡ w 2 ( mod l ) {\displaystyle q\equiv w^{2}{\pmod {l}}} w ϕ ( x , y ) {\displaystyle w\phi (x,y)} F q [ x , y ] / ( y 2 − x 3 − A x − B , ψ l ) {\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})} q ¯ ( x , y ) = w ϕ ( x , y ) {\displaystyle {\bar {q}}(x,y)=w\phi (x,y)} t l {\displaystyle t_{l}} ± 2 w ( mod l ) {\displaystyle \pm 2w{\pmod {l}}}
q が l を 法とする平方数でない 場合、 または w と のいずれに対しても式が成立しない場合 、 という仮定は 誤りとなり、 となります 。特性方程式は となります 。 − w {\displaystyle -w} ( x q 2 , y q 2 ) = + q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)} ( x q 2 , y q 2 ) = − q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)} t l = 0 {\displaystyle t_{l}=0}
追加ケース l = 2 {\displaystyle l=2} 思い出していただければ、最初の考察では の場合を省略しました。q は 奇数であると 仮定し、 特に がの位数2の元を持つ 場合のみ と仮定しているからです 。群の加法の定義により、 の位数2の元はすべて の形式でなければなりません 。したがって、 多項式が に根を持つ場合のみ 、 が の場合のみ となります 。 l = 2 {\displaystyle l=2} q + 1 − t ≡ t ( mod 2 ) {\displaystyle q+1-t\equiv t{\pmod {2}}} t 2 ≡ 0 ( mod 2 ) {\displaystyle t_{2}\equiv 0{\pmod {2}}} E ( F q ) {\displaystyle E(\mathbb {F} _{q})} ( x 0 , 0 ) {\displaystyle (x_{0},0)} t 2 ≡ 0 ( mod 2 ) {\displaystyle t_{2}\equiv 0{\pmod {2}}} x 3 + A x + B {\displaystyle x^{3}+Ax+B} F q {\displaystyle \mathbb {F} _{q}} gcd ( x q − x , x 3 + A x + B ) ≠ 1 {\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}
アルゴリズム 入力： 1. 楕円曲線 。 E = y 2 − x 3 − A x − B {\displaystyle E=y^{2}-x^{3}-Ax-B} 2.有限体 に対する 整数 q 。 F q {\displaystyle F_{q}} q = p b , b ≥ 1 {\displaystyle q=p^{b},b\geq 1} 出力： E 上 の点の数 。 F q {\displaystyle F_{q}} p を含まない 奇数素数の集合 Sを選び、 もし ならば 、 そうで なければ とする 。 除算多項式 を計算する 。 N = ∏ l ∈ S l > 4 q . {\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.} t 2 = 0 {\displaystyle t_{2}=0} gcd ( x q − x , x 3 + A x + B ) ≠ 1 {\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1} t 2 = 1 {\displaystyle t_{2}=1} ψ l {\displaystyle \psi _{l}} 以下のループのすべての計算は、 リング で実行されます。 F q [ x , y ] / ( y 2 − x 3 − A x − B , ψ l ) . {\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).} do の場合 : l ∈ S {\displaystyle l\in S} および となる 一意 の整数 とします 。 q ¯ {\displaystyle {\bar {q}}} を 計算し 、 を 計算します 。 次に 、 の場合 、 を計算します。 do の場合 : の 場合、 の 場合、 ; それ以外 の 場合: q が l を法とする平方数の場合 、 w を 計算します。 の場合、 の場合、 の場合、 で w を計算 します 。 中国 剰余 定理 を 使用 し て 、 方程式 から N を 法とする t を 計算します 。ここで、 です 。 q ≡ q ¯ ( mod l ) {\displaystyle q\equiv {\bar {q}}{\pmod {l}}} ∣ q ¯ ∣< l / 2 {\displaystyle \mid {\bar {q}}\mid <l/2} ( x q , y q ) {\displaystyle (x^{q},y^{q})} ( x q 2 , y q 2 ) {\displaystyle (x^{q^{2}},y^{q^{2}})} ( x q ¯ , y q ¯ ) {\displaystyle (x_{\bar {q}},y_{\bar {q}})} x q 2 ≠ x q ¯ {\displaystyle x^{q^{2}}\neq x_{\bar {q}}} ( X , Y ) {\displaystyle (X,Y)} 1 ≤ t ¯ ≤ ( l − 1 ) / 2 {\displaystyle 1\leq {\bar {t}}\leq (l-1)/2} X = x t ¯ q {\displaystyle X=x_{\bar {t}}^{q}} Y = y t ¯ q {\displaystyle Y=y_{\bar {t}}^{q}} t l = t ¯ {\displaystyle t_{l}={\bar {t}}} t l = − t ¯ {\displaystyle t_{l}=-{\bar {t}}} q ≡ w 2 ( mod l ) {\displaystyle q\equiv w^{2}{\pmod {l}}} w ( x q , y q ) {\displaystyle w(x^{q},y^{q})} w ( x q , y q ) = ( x q 2 , y q 2 ) {\displaystyle w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})} t l = 2 w {\displaystyle t_{l}=2w} w ( x q , y q ) = ( x q 2 , − y q 2 ) {\displaystyle w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})} t l = − 2 w {\displaystyle t_{l}=-2w} t l = 0 {\displaystyle t_{l}=0} t l = 0 {\displaystyle t_{l}=0} t ≡ t l ( mod l ) {\displaystyle t\equiv t_{l}{\pmod {l}}} l ∈ S {\displaystyle l\in S} 出力 . q + 1 − t {\displaystyle q+1-t}
複雑 計算の大部分は 、各素数 について、 およびを評価することで行われ 、つまり 、 各素数 について 、、、 を計算します 。これには、環 での累乗が含まれ 、 乗算が必要になります。 の次数は であるため 、環 の各要素は次数の多項式です 。 素数定理 により、サイズ の素数 は約 個ある ため、 となり 、 が得られます 。したがって、環 の各乗算には、 の 乗算が 必要であり 、その乗算には ビット演算が必要になります。合計で、各素数に対するビット演算の回数 は です 。この計算を各素数について実行する必要があることを考えると 、Schoof のアルゴリズムの総計算量は になります 。高速な多項式および整数演算を使用すると、この値は にまで軽減されます 。 ϕ ( P ) {\displaystyle \phi (P)} ϕ 2 ( P ) {\displaystyle \phi ^{2}(P)} l {\displaystyle l} x q {\displaystyle x^{q}} y q {\displaystyle y^{q}} x q 2 {\displaystyle x^{q^{2}}} y q 2 {\displaystyle y^{q^{2}}} l {\displaystyle l} R = F q [ x , y ] / ( y 2 − x 3 − A x − B , ψ l ) {\displaystyle R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})} O ( log q ) {\displaystyle O(\log q)} ψ l {\displaystyle \psi _{l}} l 2 − 1 2 {\displaystyle {\frac {l^{2}-1}{2}}} O ( l 2 ) {\displaystyle O(l^{2})} O ( log q ) {\displaystyle O(\log q)} O ( log q ) {\displaystyle O(\log q)} l {\displaystyle l} O ( log q ) {\displaystyle O(\log q)} O ( l 2 ) = O ( log 2 q ) {\displaystyle O(l^{2})=O(\log ^{2}q)} R {\displaystyle R} O ( log 4 q ) {\displaystyle O(\log ^{4}q)} F q {\displaystyle \mathbb {F} _{q}} O ( log 2 q ) {\displaystyle O(\log ^{2}q)} l {\displaystyle l} O ( log 7 q ) {\displaystyle O(\log ^{7}q)} O ( log q ) {\displaystyle O(\log q)} O ( log 8 q ) {\displaystyle O(\log ^{8}q)} O ~ ( log 5 q ) {\displaystyle {\tilde {O}}(\log ^{5}q)}
Schoofのアルゴリズムの改良 1990 年代に、 ノアム・エルキーズ 、続いて AOL アトキンが 、これまで検討してきた素数の集合を 特定の種類の素数に制限することで、シューフの基本アルゴリズムを改良しました。これらはそれぞれ、エルキーズ素数、アトキン素数と呼ばれるようになりました。 特性方程式 が で 分解できる素数はエルキーズ素数と呼ばれ、エルキーズ素数ではない素数はアトキン素数と呼ばれます。アトキンは、アトキン素数から得られた情報とエルキーズ素数から得られた情報を組み合わせて、 シューフ・エルキーズ・アトキン アルゴリズム と呼ばれる効率的なアルゴリズムを作成する方法を示しました。取り組むべき最初の問題は、与えられた素数がエルキーズ素数かアトキン素数かを判断することです。そのためには、 モジュラー形式の研究と、 複素数上の楕円曲線 を格子として解釈すること から生まれたモジュラー多項式を使用します 。どちらのケースであるかが分かれば、 除算多項式 の 代わりに、対応する除算多項式よりも次数の低い多項式ではなく を操作できるようになります。 効率的な実装のために、確率的な根探索アルゴリズムが使用され、これは決定論的アルゴリズムではなく ラスベガス アルゴリズム になります。ある境界までの素数の約半分が エルキーズ素数であるという経験的仮定の下では、これはシューフのアルゴリズムよりも効率的で、 単純な演算を使用した場合の予想実行時間、高速演算を使用した場合の予想実行時間を持つアルゴリズムになります。この経験的仮定はほとんどの楕円曲線に当てはまることが知られていますが、 GRH の場合でも、すべてのケースに当てはまるとは知られていません 。 S = { l 1 , … , l s } {\displaystyle S=\{l_{1},\ldots ,l_{s}\}} l {\displaystyle l} ϕ 2 − t ϕ + q = 0 {\displaystyle \phi ^{2}-t\phi +q=0} F l {\displaystyle \mathbb {F} _{l}} O ( l ) {\displaystyle O(l)} O ( l 2 ) {\displaystyle O(l^{2})} O ( log q ) {\displaystyle O(\log q)} O ( log 6 q ) {\displaystyle O(\log ^{6}q)} O ~ ( log 4 q ) {\displaystyle {\tilde {O}}(\log ^{4}q)}
実装 いくつかのアルゴリズムはMike ScottによってC++ で実装されました 。実装は無料（条件なし）で、 AGPLv3 で配布されているMIRACLライブラリを利用しています。
素数 に対する Schoof アルゴリズムの実装 。 E ( F p ) {\displaystyle E(\mathbb {F} _{p})} p {\displaystyle p} Schoof のアルゴリズムの実装 。 E ( F 2 m ) {\displaystyle E(\mathbb {F} _{2^{m}})}
参照
参考文献 R. Schoof: 有限体上の楕円曲線と平方根の計算 mod p. Math. Comp., 44(170):483–494, 1985. http://www.mat.uniroma2.it/~schoof/ctpts.pdf で入手可能 R. Schoof: 有限体上の楕円曲線上の点の数え上げ. J. Theor. Nombres Bordeaux 7:219–254, 1995. http://www.mat.uniroma2.it/~schoof/ctg.pdf で入手可能 G. Musiker: Schoof の点計算アルゴリズム 。http://www.math.umn.edu/~musiker/schoof.pdf で入手可能。 E ( F q ) {\displaystyle E(\mathbb {F} _{q})} V. ミュラー : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern.修士論文。ザールランデス大学、ザールブリュッケン、1991 年。 http://lecturer.ukdw.ac.id/vmueller/publications.php で入手可能 2020 年 7 月 28 日に ウェイバック マシンにアーカイブ A. エンゲ：楕円曲線と暗号への応用：入門 Kluwer Academic Publishers、ドルドレヒト、1999年。 LCワシントン著『楕円曲線：数論と暗号』Chapman & Hall/CRC、ニューヨーク、2003年。 N. コブリッツ：数論と暗号学講座、大学院数学テキスト第114号、シュプリンガー・フェアラーク、1987年。第2版、1994年
![{\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df597463920086a0c5eedd53bfa0fd1d6d6f6f31)
![{\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5996229b7aca2eb8db099446f76fbe02863ba58b)
![{\displaystyle E[l]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d142b213b9204c3ce400e38123d6355df185d22)
![{\displaystyle [-(l-1)/2,(l-1)/2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/661281ac9fe6d7581b92c46ea8df4e202c051fbe)
![{\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50db1f8ee0f66530a05e2e7befaa5dfe3cb85c11)
![{\displaystyle {\bar {t}}\in [0,(l-1)/2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53702d5a22870224c937fb6f9913a1daad0b9778)
![{\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b861d0709222a3992ed05c9b60c175c3e877668d)
![{\displaystyle R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76c799e0c50c2b4bce7d3510c0b5bba64cd0463c)
