７．楕円曲線法 (Elliptic Curve Method)

まずは楕円曲線の定義から。
P² (２次元実射影平面) 上の点の (x, y) で、以下の式を満たすものの集合を楕円曲線と呼ぶ。

y² = x³ + ax + b

左辺の２乗が無ければ、ただの３次式 (３次曲線) である。
よって、上の楕円曲線の概形は、

x³ + ax + b ≥ 0

となる部分を、x 軸を中心に折り返したような形となる。

楕円曲線上の２点、p₁(x₁,y₁)、p₂(x₂,y₂) に対して、
点 p₃(x₃,y₃) を対応させる演算を、以下のように定義する。

• x₁≠x₂ のとき、

λ = (y₂ - y₁)/(x₂ - x₁)
ν = (y₁x₂ - y₂x₁)/(x₂ - x₁)

• x₁ = x₂、y₁ = y₂ ≠ 0 のとき、

λ = (3x₁² + a)/2y₁
ν = ( - x₁³ + ax₁ + 2b)/2y₁

とし、

x₃ = λ² - x₁ - x₂
y₃ = - λx₃ - ν

とする。また、

• x₁ = x₂、y₁ = - y₂ のとき、

p₃ = O (無限遠点)

とする。

この演算によって、楕円曲線上の点は、群となり、かつ、この演算は可換 (交換可能) なので、
楕円曲線上の点は、この演算により加法群をなす。
(ここで、群とは何か、という説明はしない。要するに群の中の任意の点について、この演算が成り立って、
かつ、その結果がまた群に属する、ということだと思って欲しい。)

上の定義を mod p で考える。割り算の部分は、mod p の逆数の掛け算とする。

群の要素 (元) については、以下の定理が一般に成り立つ。

群の元の個数が有限のとき、有限群と呼ぶ。
有限群の任意の元 x について、ある数 e が存在し、x^e = 1 (単位元)。
演算が加法の時は、ex = x + x + …… + x (e個の足し算) = 0 となる。
特に、元の個数を m とすると、任意の元について、mx = 0

ここで、p-1 method のときと同じ方法をとる。
まず、m を固定する。p-1のときのように小さい素数の積とする。
適当な a, b, p(x,y) を出発点にして、mp を計算する (mod ｎ で計算する) 。
計算の途中で分母が 0 となったとき、分母と n の gcd をとることにより、素因数が求められる。
この方法を楕円曲線法 (Elliptic Curve Method) と呼ぶ。

p-1 では、見つからなかった場合、m の値を大きくするしか手がなかったため、
ある値以上は、実質的に計算が不可能になった。
楕円曲線法では、m の他に、a, b を変えるという手があるので、
処理時間の増大を防ぐことができる。

これについても、コーディング例は示さない。
詳細は、

木田祐司、牧野潔夫「UBASICによるコンピュータ整数論」(株)日本評論社 (1994)

参照のこと。