楕円曲線 の研究における重要な側面は、 曲線上の点を数える 効率的な方法を考案することです 。これを行うためのアプローチはいくつかあり、考案された アルゴリズムは 、数論 、さらに最近では 暗号 やデジタル署名認証 などのさまざまな分野の研究で有用なツールであることが証明されています ( 楕円曲線暗号 と 楕円曲線 DSAを参照)。数論では、これらのアルゴリズムは ディオファントス方程式 を解く際に重要な結果をもたらしますが 、暗号に関しては、 有限体 上の楕円曲線の群 に対する 離散対数問題 (DLP) の困難さを効果的に利用することができます。ここで、 q = p k であり 、 p は 素数です。DLP として知られるようになった方法は、 公開鍵暗号 に広く使用されているアプローチであり、この問題を解く困難さによって暗号システムの セキュリティ レベル が決まります。この記事では、特に p > 3 の大きな特性を持つ体上の楕円曲線上の点をカウントするアルゴリズムについて説明します。小さな特性を持つ体上の曲線の場合、 p 進法 に基づくより効率的なアルゴリズムが 存在します。
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
ふ
q
{\displaystyle \mathbb {F} _{q}}
楕円曲線上の点を数えるアプローチ この問題にはいくつかのアプローチがあります。まずは素朴なアプローチから始めて、このテーマに関する Schoof の決定的な研究までの発展をたどり、同時に Elkies (1990) と Atkin (1992) による Schoof のアルゴリズムの改良についても説明します。
いくつかのアルゴリズムでは、形式の群は ハッセの重要な定理に従うという事実を利用しており、この定理は考慮する点の数を制限する。 ハッセの定理は、 Eが 有限体上の楕円曲線である場合 、の 濃度 が 以下を満たすこと
を述べている。
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
ふ
q
{\displaystyle \mathbb {F} _{q}}
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
|
|
え （
ふ
q
）
|
− （ q + 1 ）
|
≤ 2
q
。
{\displaystyle ||E(\mathbb {F} _{q})|-(q+1)|\leq 2{\sqrt {q}}.\,}
素朴なアプローチ 最も洗練されていない点を数える単純なアプローチは、体のすべての要素を調べ 、どの要素が楕円曲線のワイエルシュトラス形式を満たすかをテストする
ことです。
ふ
q
{\displaystyle \mathbb {F} _{q}}
ええ
2
=
x
3
+ あ x + B 。
{\displaystyle y^{2}=x^{3}+Ax+B.\,}
例 E を y 2 = x 3 + x + 1 上の 曲線と します 。 E上の点を数えるには、 x の可能な値 、次にx mod 5 の 平方剰余 (検索目的のみ)、次に x 3 + x + 1 mod 5 の平方剰余、最後に x 3 + x + 1 mod 5の yのリストを作成します。これにより、 E 上の点が生成されます 。
ふ
5
{\displaystyle \mathbb {F} _{5}}
たとえば、最後の行は次のように計算されます。 方程式に x 3 + x + 1 mod 5 を挿入すると、結果として (3 列目) が得られます。この結果は、 ( 2 列目では 平方剰余 を調べることができます)の場合に達成できます 。したがって、最後の行のポイントは です 。
x = 4
{\displaystyle x=4}
4
{\displaystyle 4}
ええ = 2 、 3
{\displaystyle y=2,3}
（ 4 、 2 ） 、 （ 4 、 3 ）
{\displaystyle (4,2),(4,3)}
したがって、の基数 は 9 です。つまり、 前にリストした 8 つの点と無限遠点
です。
え （
ふ
5
）
{\displaystyle E(\mathbb {F} _{5})}
このアルゴリズムでは、 のすべての値 を考慮する必要がある
ため、 実行時間 O ( q ) が必要です。
x ∈
ふ
q
{\displaystyle x\in \mathbb {F} _{q}}
小さな一歩、大きな一歩 別のアプローチを使用すると、実行時間の改善が実現します。 が の平方になるまで のランダムな値を選択して要素を選択し 、次に を得るためにこの値の平方根を計算します。ハッセの定理によれば、 は 区間 内 に あり ます 。したがって、 ラグランジュの定理 により、この区間内にあり を満たす 唯一の を見つけることは 、 の濃度を見つけることにつながります。 となる区間内に と という 2 つの異なる整数が存在する場合、アルゴリズムは失敗します 。このような場合は通常、 内の別のランダムに選択された点でアルゴリズムを繰り返すだけで十分です 。
ポ = （ x 、 ええ ） ∈ え （
ふ
q
）
{\displaystyle P=(x,y)\in E(\mathbb {F} _{q})}
x
{\displaystyle x}
x
3
+ あ x + B
{\displaystyle x^{3}+Ax+B}
ふ
q
{\displaystyle \mathbb {F} _{q}}
ええ
{\displaystyle y}
|
え （
ふ
q
）
|
{\displaystyle |E(\mathbb {F} _{q})|}
（ q + 1 − 2
q
、 q + 1 + 2
q
）
{\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}
ま
{\displaystyle M}
ま ポ = お
{\displaystyle MP=O}
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
ま
{\displaystyle M}
ま ′
{\displaystyle M'}
ま ポ =
ま ′
ポ = お
{\displaystyle MP=M'P=O}
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
を満たす値を見つけるために の すべての値を試すには、 約 ステップかかります。
ま
{\displaystyle M}
ま ポ = お
{\displaystyle MP=O}
4
q
{\displaystyle 4{\sqrt {q}}}
しかし、 ベイビーステップ ジャイアントステップ アルゴリズムを に適用すると 、これを約 ステップまで高速化できます 。アルゴリズムは次のとおりです。
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
4
q
4
{\displaystyle 4{\sqrt[{4}]{q}}}
アルゴリズム 1. 整数を選択する、
2. FOR { to } DO
3.
4. ENDFOR
5.
6.
7. REPEAT ポイントを計算する
8. UNTIL : \\ -座標が比較される
メートル
{\displaystyle m}
メートル >
q
4
{\displaystyle m>{\sqrt[{4}]{q}}}
じ = 0
{\displaystyle j=0}
メートル
{\displaystyle m}
ポ
じ
← じ ポ
{\displaystyle P_{j}\leftarrow jP}
ら ← 1
{\displaystyle L\leftarrow 1}
質問 ← （ q + 1 ） ポ
{\displaystyle Q\leftarrow (q+1)P}
質問 + け （ 2 メートル ポ ）
{\displaystyle Q+k(2mP)}
∃ じ
{\displaystyle \exists j}
質問 + け （ 2 メートル ポ ） = ±
ポ
じ
{\displaystyle Q+k(2mP)=\pm P_{j}}
x
{\displaystyle x}
9. \\note
10. 因数 。 を の異なる素因数とします 。
ま ← q + 1 + 2 メートル け ∓ じ
{\displaystyle M\leftarrow q+1+2mk\mp j}
ま ポ = お
{\displaystyle MP=O}
ま
{\displaystyle M}
p
1
、 … 、
p
r
{\displaystyle p_{1},\ldots ,p_{r}}
ま
{\displaystyle M}
11. WHILE DO
12. IF
13. THEN
14. ELSE
15. ENDIF
16. ENDWHILE
17. \\note は ポイントの順序です
18. WHILE は 複数の整数を割ります 19. DO 新しいポイントを選択し
て 1 に進みます。
私 ≤ r
{\displaystyle i\leq r}
ま
p
私
ポ = お
{\displaystyle {\frac {M}{p_{i}}}P=O}
ま ←
ま
p
私
{\displaystyle M\leftarrow {\frac {M}{p_{i}}}}
私 ← 私 + 1
{\displaystyle i\leftarrow i+1}
ら ← 1cmあたり （ ら 、 ま ）
{\displaystyle L\leftarrow \operatorname {lcm} (L,M)}
ま
{\displaystyle M}
ポ
{\displaystyle P}
ら
{\displaystyle L}
いいえ
{\displaystyle N}
（ q + 1 − 2
q
、 q + 1 + 2
q
）
{\displaystyle (q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})}
ポ
{\displaystyle P}
20. ENDWHILE
21. RETURN \\これは、
いいえ
{\displaystyle N}
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
アルゴリズムに関する注記 8 行目では、一致が存在することを前提としています。実際、次の補題はそのような一致が存在することを保証します。 を の整数とし ます。 の整数 と が 存在する。
1つの
{\displaystyle a}
|
1つの
|
≤ 2
メートル
2
{\displaystyle |a|\leq 2m^{2}}
1つの
0
{\displaystyle a_{0}}
1つの
1
{\displaystyle a_{1}}
− メートル <
1つの
0
≤ メートル
そして
− メートル ≤
1つの
1
≤ メートル
st
1つの =
1つの
0
+ 2 メートル
1つの
1
。
{\displaystyle -m<a_{0}\leq m{\mbox{ かつ }}-m\leq a_{1}\leq m{\mbox{ st }}a=a_{0}+2ma_{1}.}
を一度 計算すると 、完全なスカラー乗算を新たに計算する代わりに、 を加算することで計算できます。したがって、完全な計算には加算が必要です 。 は、 から 1 回の倍算で得られます 。 の計算には、 倍算と 加算が 必要です。ここで、 は の 2 進表現の非ゼロの桁数です 。 と を知っていると 、 倍算の回数を減らすことができることに注意してください。最後に、 から を取得するには 、 すべてを再計算するのではなく、 単に加算します。
（ じ + 1 ） ポ
{\displaystyle (j+1)P}
じ ポ
{\displaystyle jP}
ポ
{\displaystyle P}
じ ポ
{\displaystyle jP}
メートル
{\displaystyle m}
2 メートル ポ
{\displaystyle 2mP}
メートル ポ
{\displaystyle mP}
質問
{\displaystyle Q}
ログ （ q + 1 ）
{\displaystyle \log(q+1)}
わ
{\displaystyle w}
わ
{\displaystyle w}
q + 1
{\displaystyle q+1}
じ ポ
{\displaystyle jP}
2 メートル ポ
{\displaystyle 2mP}
質問 + け （ 2 メートル ポ ）
{\displaystyle Q+k(2mP)}
質問 + （ け + 1 ） （ 2 メートル ポ ）
{\displaystyle Q+(k+1)(2mP)}
2 メートル ポ
{\displaystyle 2mP}
ここでは を因数分解できるものと仮定しています 。 できない場合は、少なくともすべての小さな素因数を見つけて 、 これらについて であることを確認できます。 すると は の 順序 の良い候補になります 。
ま
{\displaystyle M}
p
私
{\displaystyle p_{i}}
ま
p
私
≠ お
{\displaystyle {\frac {M}{p_{i}}}\neq O}
ま
{\displaystyle M}
ポ
{\displaystyle P}
ステップ 17 の結論は、初等群論を使用して証明できます。 であるため 、 の位数は を割り切れます 。 の適切な約数が を実現しない場合 、 は の位数です 。
ま ポ = お
{\displaystyle MP=O}
ポ
{\displaystyle P}
ま
{\displaystyle M}
ま ¯
{\displaystyle {\bar {M}}}
ま
{\displaystyle M}
ま ¯
ポ = お
{\displaystyle {\bar {M}}P=O}
ま
{\displaystyle M}
ポ
{\displaystyle P}
この方法の欠点の 1 つは、グループが大きくなると大量のメモリが必要になることです。これに対処するには、 点の座標のみ (対応する整数 とともに) を保存する方が効率的かもしれません。ただし、これにより 、 と を選択するための余分なスカラー乗算が必要になります 。
x
{\displaystyle x}
じ ポ
{\displaystyle jP}
じ
{\displaystyle j}
− じ
{\displaystyle -j}
+ じ
{\displaystyle +j}
ポラードのローアルゴリズム や ポラードカンガルー 法など、よりスペース効率の高いグループ要素の順序を計算するための他の汎用アルゴリズムがあります 。ポラードカンガルー法では、指定された間隔で解を検索することができ、実行時間は で 、 スペースが使用されます。
お （
q
4
）
{\displaystyle O({\sqrt[{4}]{q}})}
お （
ログ
2
q
）
{\displaystyle O(\log^{2}{q})}
シューフのアルゴリズム 型の群の濃度を計算する問題に対する理論的な躍進は、1985 年に最初の決定論的多項式時間アルゴリズムを発表した René Schoof によって達成されました。Schoof のアルゴリズムの中心となるのは 、除算多項式 と ハッセの定理 、および 中国剰余定理 の使用です 。
え （
ふ
q
）
{\displaystyle E(\mathbb {F} _{q})}
Schoof の洞察は、ハッセの定理により、 の可能な値の範囲が有限であるという事実を利用しています。 整数 を法 として計算するだけで十分です。これは、 積が を超える 素数を 法として計算し、次に中国剰余定理を適用することで実現されます 。アルゴリズムの鍵となるのは、除算多項式を使用して を 法として効率的に計算すること です 。
|
え （
ふ
q
）
|
{\displaystyle |E(\mathbb {F} _{q})|}
|
え （
ふ
q
）
|
{\displaystyle |E(\mathbb {F} _{q})|}
いいえ > 4
q
{\displaystyle N>4{\sqrt {q}}}
|
え （
ふ
q
）
|
{\displaystyle |E(\mathbb {F} _{q})|}
ℓ
1
、 … 、
ℓ
s
{\displaystyle \ell _{1},\ldots ,\ell _{s}}
4
q
{\displaystyle 4{\sqrt {q}}}
ψ
ℓ
{\displaystyle \psi_{\ell}}
|
え （
ふ
q
）
|
{\displaystyle |E(\mathbb {F} _{q})|}
ℓ
{\displaystyle \ell}
Schoof アルゴリズムの実行時間は の多項式で 、漸近複雑度はです 。ここで、 は 整数乗算 の複雑度 を表します 。その空間複雑度は です 。
ん = ログ
q
{\displaystyle n=\log {q}}
O
(
n
2
M
(
n
3
)
/
log
n
)
=
O
(
n
5
+
o
(
1
)
)
{\displaystyle O(n^{2}M(n^{3})/\log {n})=O(n^{5+o(1)})}
M
(
n
)
{\displaystyle M(n)}
O
(
n
3
)
{\displaystyle O(n^{3})}
Schoof-Elkies-Atkin アルゴリズム 1990 年代に、 Noam Elkies が 、続いて AOL Atkin が、 使用される 素数を区別することで Schoof の基本アルゴリズムを改良しました。素数は 、フロベニウス自己準同型 の特性方程式が で分割される場合、Elkies 素数と呼ばれます 。それ以外の場合、 Atkin 素数と呼ばれます。Elkies 素数は、Schoof のアルゴリズムの漸近的複雑性を改善する鍵です。Atkin 素数から得られる情報により、漸近的には無視できるものの、実用上非常に重要になる可能性があるさらなる改善が可能になります。Schoof のアルゴリズムを Elkies 素数と Atkin 素数を使用するように修正したものは、Schoof–Elkies–Atkin (SEA) アルゴリズムとして知られています。
ℓ
1
,
…
,
ℓ
s
{\displaystyle \ell _{1},\ldots ,\ell _{s}}
ℓ
{\displaystyle \ell }
ϕ
2
−
t
ϕ
+
q
=
0
{\displaystyle \phi ^{2}-t\phi +q=0}
F
ℓ
{\displaystyle \mathbb {F} _{\ell }}
ℓ
{\displaystyle \ell }
特定の素数のステータスは 楕円曲線 に依存し 、 モジュラ多項式 を 使用して決定できます。一変数多項式が （ は の j 不変量 を表す） に根を持つ場合、 は エルキーズ素数であり、そうでない場合はアトキン素数です。エルキーズの場合、モジュラ多項式を含むさらなる計算を使用して、除算多項式 の適切な因数を取得します 。この因数の次数は ですが 、 の 次数は です 。
ℓ
{\displaystyle \ell }
E
/
F
q
{\displaystyle E/\mathbb {F} _{q}}
Ψ
ℓ
(
X
,
Y
)
{\displaystyle \Psi _{\ell }(X,Y)}
Ψ
ℓ
(
X
,
j
(
E
)
)
{\displaystyle \Psi _{\ell }(X,j(E))}
F
q
{\displaystyle \mathbb {F} _{q}}
j
(
E
)
{\displaystyle j(E)}
E
{\displaystyle E}
ℓ
{\displaystyle \ell }
ψ
ℓ
{\displaystyle \psi _{\ell }}
O
(
ℓ
)
{\displaystyle O(\ell )}
ψ
ℓ
{\displaystyle \psi _{\ell }}
O
(
ℓ
2
)
{\displaystyle O(\ell ^{2})}
Schoof のアルゴリズムとは異なり、SEA アルゴリズムは、通常、 確率アルゴリズム ( ラスベガス 型) として実装されるため、根探索やその他の操作をより効率的に実行できます。その計算複雑性は、モジュラー多項式 を計算するコストによって大きく左右されます が、これらは に依存しないため 、一度計算して再利用できます。十分な数の小さな Elkies 素数が存在するという経験的仮定の下で、モジュラー多項式を計算するコストを除けば、SEA アルゴリズムの漸近的実行時間は です ( ただし ) 。その空間複雑性は です が、事前に計算されたモジュラー多項式を使用すると、 に増加します 。
Ψ
ℓ
(
X
,
Y
)
{\displaystyle \Psi _{\ell }(X,Y)}
E
{\displaystyle E}
O
(
n
2
M
(
n
2
)
/
log
n
)
=
O
(
n
4
+
o
(
1
)
)
{\displaystyle O(n^{2}M(n^{2})/\log {n})=O(n^{4+o(1)})}
n
=
log
q
{\displaystyle n=\log {q}}
O
(
n
3
log
n
)
{\displaystyle O(n^{3}\log {n})}
O
(
n
4
)
{\displaystyle O(n^{4})}
参照
文献 I. Blake、G. Seroussi、N. Smart: 暗号化における楕円曲線 、ケンブリッジ大学出版局、1999 年。 A. Enge: 楕円曲線と暗号への応用: 入門 Kluwer Academic Publishers、ドルドレヒト、1999 年。 G. Musiker: 上の点を数えるための Schoof のアルゴリズム 。http://www.math.umn.edu/~musiker/schoof.pdf で入手可能。
E
(
F
q
)
{\displaystyle E(\mathbb {F} _{q})}
R. Schoof: 有限体上の楕円曲線上の点の計算。J. Theor. Nombres Bordeaux 7:219-254、1995。http://www.mat.uniroma2.it/~schoof/ctg.pdf で入手可能。 LC Washington: 楕円曲線: 数論と暗号。Chapman \& Hall/CRC、ニューヨーク、2003 年。
参考文献
![{\displaystyle 4{\sqrt[{4}]{q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/495c5b6948d76fd8c8445effd8bb9b9e20f64262)
![{\displaystyle m>{\sqrt[{4}]{q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c006dbed41ca9cdb6f040d0b2994b42b9a0f5005)
![{\displaystyle O({\sqrt[{4}]{q}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4182beb722873e136c8cdbed3199b0a53d1c3271)
