12章 素因数分解アルゴリズム

７．楕円曲線法 (Elliptic Curve Method) まずは楕円曲線の定義から。 P2 (２次元実射影平面) 上の点の (x, y) で、以下の式を満たすものの集合を楕円曲線と呼ぶ。 y2 = x3 + ax + b 左辺の２乗が無ければ、ただの３次式 (３次曲線) である。 よって、上の楕円曲線の概形は、 x3 + ax + b ≥ 0 となる部分を、x 軸を中心に折り返したような形となる。 楕円曲線上の２点、p1(x1,y1)、p2(x2,y2) に対して、 点 p3(x3,y3) を対応させる演算を、以下のように定義する。 x1≠x2 のとき、 λ = (y2 - y1)/(x2 - x1) ν = (y1x2 - y2x1)/(x2 - x1) x1 = x2、y1 = y2 ≠ 0 のとき、 λ = (3x12 + a)/2y1 ν = ( - x13 + ax1 +