シューフのアルゴリズムは、 有限体 上の 楕円曲線 上の点を数える効率的なアルゴリズムです 。このアルゴリズムは、楕円曲線上の点の グループ における 離散対数問題を 解く難しさを判断するために点の数を知ることが重要となる 楕円曲線暗号 に応用されています。
このアルゴリズムは 1985 年にRené Schoof によって発表されました。 楕円曲線上の点を数える 最初の決定論的多項式時間アルゴリズムであったため、理論的には画期的なものでした。Schoofのアルゴリズム以前は、ナイーブ アルゴリズムや ベイビー ステップ ジャイアント ステップ アルゴリズムなど、楕円曲線上の点を数えるアプローチは 、ほとんどの場合、面倒で実行時間が指数関数的でした。
この記事では、アルゴリズムの構造の根底にある数学的な考え方に重点を置いて、Schoof のアプローチについて説明します。
導入 を有限体 上で定義された 楕円曲線 と する。 ここで 、 は 素数、 は 整数である 。特性 の体上では、 楕円曲線は（短い）ワイエルシュトラス方程式で与えられる。
え
{\displaystyle E}
ふ
q
{\displaystyle \mathbb {F} _{q}}
q =
p
ん
{\displaystyle q=p^{n}}
p
{\displaystyle p}
ん
{\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}}}
素数 を 計算するために、フロベニウス自己準同型性 と 除算多項式 の理論を利用します 。 積が十分に大きくなるように、常により大きな素数をその場所に選択できるため、素数を検討しても損失はありません。いずれにしても、小さな特性の体には より効率的な、いわゆる adic アルゴリズムがあるため、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
では 最大で1 であることを意味します 。
(
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 座標を使用して、2 つのケースのどちらが当てはまるかを判断します。
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
)
)
{\displaystyle (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))}
そしてそれを持っている
X
(
x
)
≡
(
x
3
+
A
x
+
B
)
(
(
x
3
+
A
x
+
B
)
q
2
−
1
2
−
θ
(
x
)
)
mod
ψ
l
(
x
)
.
{\displaystyle X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x)){\bmod {\psi }}_{l}(x).}
ここで、それは正しくないようです、私たちは捨てますか ？
x
q
2
−
x
q
¯
{\displaystyle x^{q^{2}}-x_{\bar {q}}}
さて、 1つが 満たされる
場合
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 と を使用すると、 ( または) の 2 つの値のどちらが機能するかを判断できます 。これにより、 の値が得られます。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を選び、 if 、 else とします 。 除算多項式を計算します 。
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}}}
。 を計算し 、 を計算します 。 if then を計算します 。 for do の場合 : if then if then ; else . else if q が l を 法 と する平方数で ある場合は、 w を計算します。 if then else if then else else 中国剰余定理を
使用して、
方程式 から 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 年代に、 Noam Elkies 氏 、続いて AOL Atkin 氏が、Schoof の基本アルゴリズムの改良点として、これまで検討してきた素数の集合を 特定の種類の素数に制限する方法を考案しました。これらはそれぞれ、Elkies 素数、Atkin 素数と呼ばれるようになりました。素数の 特性方程式 が で 分割される 場合、その素数は Elkies 素数と呼ばれ、Atkin 素数は Elkies 素数ではない素数と呼ばれます。Atkin 氏は、Atkin 素数から得られる情報と Elkies 素数から得られる情報を組み合わせて、Schoof –Elkies–Atkin アルゴリズムと呼ばれる効率的なアルゴリズムを作成する方法を示しました。取り組むべき最初の問題は、与えられた素数が Elkies 素数か Atkin 素数かを判断することです。そのためには、 モジュラー形式 の研究と、複素数 上の格子としての楕円曲線 の解釈から生まれたモジュラー多項式を使用します 。どちらのケースであるかがわかれば、 除算多項式 を使用する代わりに、対応する除算多項式よりも次数の低い多項式 ではなくを使用できます 。効率的な実装のために、確率的な根探索アルゴリズムが使用され、これは決定論的アルゴリズムではなく ラスベガス アルゴリズム になります。ある境界までの素数の約半分が エルキー素数であるという経験的仮定の下では、これはシューフのアルゴリズムよりも効率的で、 素朴な演算を使用した場合の予想実行時間 、高速演算を使用した場合の予想実行時間 であるアルゴリズムを生み出します。この経験的仮定はほとんどの楕円曲線に当てはまることが知られていますが、 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 で入手可能 A. Enge: 楕円曲線と暗号への応用: 入門 Kluwer Academic Publishers、ドルドレヒト、1999 年。 LC ワシントン: 楕円曲線: 数論と暗号。Chapman & Hall/CRC、ニューヨーク、2003 年。 N. コブリッツ: 数論と暗号学のコース、大学院数学テキスト第 114 号、Springer-Verlag、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)
