まずは楕円曲線の定義から。
P2 (2次元実射影平面) 上の点の (x, y) で、以下の式を満たすものの集合を楕円曲線と呼ぶ。
y2 = x3 + ax + b
左辺の2乗が無ければ、ただの3次式 (3次曲線) である。
よって、上の楕円曲線の概形は、
x3 + ax + b ≥ 0
となる部分を、x 軸を中心に折り返したような形となる。
楕円曲線上の2点、p1(x1,y1)、p2(x2,y2) に対して、
点 p3(x3,y3) を対応させる演算を、以下のように定義する。
λ = (y2 - y1)/(x2 - x1)
ν = (y1x2 - y2x1)/(x2 - x1)
λ = (3x12 + a)/2y1
ν = ( - x13 + ax1 + 2b)/2y1
とし、
x3 = λ2 - x1 - x2
y3 = - λx3 - ν
とする。また、
p3 = O (無限遠点)
とする。
この演算によって、楕円曲線上の点は、群となり、かつ、この演算は可換 (交換可能) なので、
楕円曲線上の点は、この演算により加法群をなす。
(ここで、群とは何か、という説明はしない。要するに群の中の任意の点について、この演算が成り立って、
かつ、その結果がまた群に属する、ということだと思って欲しい。)
上の定義を mod p で考える。割り算の部分は、mod p の逆数の掛け算とする。
群の要素 (元) については、以下の定理が一般に成り立つ。
群の元の個数が有限のとき、有限群と呼ぶ。
有限群の任意の元 x について、ある数 e が存在し、xe = 1 (単位元)。
演算が加法の時は、ex = x + x + …… + x (e個の足し算) = 0 となる。
特に、元の個数を m とすると、任意の元について、mx = 0
ここで、p-1 method のときと同じ方法をとる。
まず、m を固定する。p-1のときのように小さい素数の積とする。
適当な a, b, p(x,y) を出発点にして、mp を計算する (mod n で計算する) 。
計算の途中で分母が 0 となったとき、分母と n の gcd をとることにより、素因数が求められる。
この方法を楕円曲線法 (Elliptic Curve Method) と呼ぶ。
p-1 では、見つからなかった場合、m の値を大きくするしか手がなかったため、
ある値以上は、実質的に計算が不可能になった。
楕円曲線法では、m の他に、a, b を変えるという手があるので、
処理時間の増大を防ぐことができる。
これについても、コーディング例は示さない。
詳細は、
木田祐司、牧野潔夫「UBASICによるコンピュータ整数論」(株)日本評論社 (1994)
参照のこと。
前 | この章の目次 |
---|