Schoof のアルゴリズム

1. はじめに

今後書く予定の ECPP に関する記事*1の前準備としてしたためました.

2. 理論

有限体  \mathbb{F}_q 上で定義される楕円曲線  E: y^2 = x^3 + ax + b の Abel 群を考えます. \# E(\mathbb{F}_q),すなわち  E \mathbb{F}_q-有理点の数をうまく数えるのが目標です.

Schoof のアルゴリズム楕円曲線の位数計算アルゴリズムとしてよく使われるものになります.これは中国人剰余定理(CRT)に立脚しています.

Hasse の定理

 E/\mathbb{F}_q\mathbb{F}_q 上で定義された楕円曲線とすると, \mid \#E - (q + 1) \mid \le 2 \sqrt{q}

この定理は何を言っているかというと, E はだいたい  q - 1 個くらいの点を持っており,誤差は  \pm 2 \sqrt{q} くらいに収まる,ということです.

しかしいまは  \# E正確に求めたいので,この定理で満足するわけにはいきません.それでも,この Hasse の定理をテコにして考える,ということが楕円曲線関連ではよく行われます.

たとえば,Legendre の記号を使って考えると,

 \displaystyle{ \# E = 1 + \sum_{x \in \mathbb{F}_q} \left\{ 1 + \left( \frac{f(x)}{q} \right) \right\} = 1 + q + \sum_{x \in \mathbb{F}_q} \left( \frac{f(x)}{q} \right) }

であり,

 \displaystyle{  \sum_{x \in \mathbb{F}_q} \left( \frac{f(x)}{q} \right) \le 2\sqrt{q}}

が成り立ちます.そしてこのような総和は平方剰余の相互法則を使ってうまく計算できます.これは位数計算アルゴリズムとしてはもっとも簡単なものです.

もう一つ用語を導入しておきましょう.

Frobenius 写像

 \phi : (x, y) \to (x^q, y^q) を Frobenius 写像と呼ぶ.Frobenius 写像のトレースを  t = q + 1 - \# E(\mathbb{F}_q) によって定める.

この辺の議論も面白いんですがここに書くと脱線するので気になる人は AEC とかを読んでください.

Schoof のアルゴリズムのアイデアは小さな  l_1, l_2, \cdots , l_i, \cdots に対して  t \bmod l_i を計算し,CRT と Euclid の互除法から  t を復元することにあります.どのくらいの  l_i について見ればいいかというと,

 \displaystyle{ \prod_{2 \le l_i \le l_{\mathrm{max}}} l_i > 4\sqrt{q}}

を満たすような最小の  l_{\mathrm{max}} まででよく,このとき用意すべき素数の個数は,素数定理より  \log q / \log \log q くらいで与えられます.

 t \bmod l_i を計算するさいのこまごまとしたテクニックにはここでは触れません.実装もやりません.

Schoof のアルゴリズムのすごい点は,これが初の多項式時間位数計算アルゴリズムであることです.時間計算量は  O( (\log q)^8 ) だそうです.現在では  l_i を Elkies 素数と Atkins 素数に分類することで高速化を図った Schoof-Elkies-Atkin 法が使われます.

*1:書かないかもしれません.