Factoring with Elliptic Curves Method

[2001.03.22]楕円曲線を使った素因数分解

楕円曲線を使った素因数分解プログラム(Common LISP版)
楕円曲線を使った素因数分解プログラム(ruby版)

1.楕円曲線とは

楕円曲線は、３次または４次の代数方程式
  y²=x³+ax²+bx+c  (Weierstrassの標準形) ---- (1)
または
  y²=ax³+bx²+cx+d (ただし、a≠0) ---- (2)
または
  y²=ax⁴+bx³+cx²+dx+e (ただし、a≠0) ---- (3)
で定義される曲線である。ここでx,yは有理数体Ｑ,複素数体Ｃ,代数体などの元として考える。

Weierstrassの標準形(1)では、右辺はxの３次式でx³の係数は１となっている。
(2)では、x³の係数はaであるが、双有理変換
    X=ax,
    Y=a²y
つまり、
    x=X/a,
    y=Y/a²
によって、Weierstrassの標準形
    Y²=X³+a³bX²+a³cX+a³d
に変形できる。
(3)のように、右辺がxの４次式の場合でも、ある双有理変換を通して、上記の標準形に帰着できる。

以下では、右辺が３次式のWeierstrass標準形の楕円曲線のみを扱う。
(1)の右辺の３次式の判別式は
    D=-4a³c+a²b²+18abc-4b³-27c²
である。
D≠0の場合、この曲線を非特異楕円曲線と呼ぶが、これは、種数１の代数曲線と同値である。
D＝0の場合は、特異楕円曲線と呼ぶ。
ここで、種数とは、x,yを複素数で考えた場合に、これらの曲線(浮輪のような閉曲面になる)の穴の数である。
楕円曲線上の点(x,y)について、x,yが共に有理整数であるものを整点と呼び、x,yが共に有理数であるものを有理点と呼ぶ。Diophantus方程式(1)の(有理)整数解や有理数解を求めることは、その代数曲線上の整点や有理点を求めることと同値である。

2.楕円曲線上の点に対する-,+,*演算

楕円曲線C上の点P,Qに対して、同じ曲線C上の点-P,P+Q,P*Qを次のように定義することができる。

-Pは、Pをx軸に対して、反転させた点とする。
P*Qは、直線PQと楕円曲線Cのもう一つの交点とする。
P+Qは、-(P*Q)とする。

定義より直ちに、楕円曲線C上の任意の点P,Q,Rに対して、
  P+Q=Q+P,
  P*Q=Q*P,
  (P+Q)+R=P+(Q+R),
  (P*Q)*R=P*(Q*R)
が成立する。
また、(y軸方向の)無限遠点Oも楕円曲線C上の点と考えると、
  O+P=P+O=P,
  P+(-P)=(-P)+P=O
が成立する。

楕円曲線y²=x³+ax²+bx+c上の点P(x₁,y₁),Q(x₂,y₂)について、(P*Q)(x₃,y₃)を具体的に計算すると、
  λ=(y₂-y₁)/(x₂-x₁)  if x₁≠x₂
     =(3x₁²+2ax₁+b)/2y₁    if x₁=x₂
  ν=y₁-λx₁=y₂-λx₂
として、
  x₃=λ²-a-x₁-x₂
  y₃=λx₃+ν
となる。よって、(P+Q)(x₃,-y₃)となる。

3.楕円曲線上のk倍点,位数

楕円曲線C上の点Pに対して、P+Pを2Pと書き、Pの２倍点と呼ぶ。
楕円曲線 y²=x³+ax²+bx+c上の点P(x,y)の２倍点を2P(x₂,y₂)とすると、
y!=0のとき、
  x₂ = λ²-2x-a
  y₂ = -(λ³-λ²(2x+a)+ν)
ただし
  λ = {3x²+2ax+b}/{2y}
  ν = {-x³+bx+c}/{2y}

つまり、
  x₂ = ({3x²+2ax+b}/{2y})²-2x-a
  y₂ = -(({3x²+2ax+b}/{2y})³-(2x+a)({3x²+2ax+b}/{2y})+{-x³+bx+c}/{2y})
となる。
同様に、3P=2P+P,4P=3P+P,5P=4P+P,...,kP=(k-1)P+P,...をPの３倍点, ４倍点,５倍点,...,k倍点,...と呼ぶ。
kP=Oとなる最小の自然数kが存在する場合、kをPの位数(order)と呼ぶ。また、Pを有限位数の点(ねじれ点)と呼ぶ。
kP=Oとなる自然数kが存在しない場合、Pを無限位数の点と呼ぶ。
楕円曲線上でy座標が0の点P(x,0)は、P=-Pつまり2P=Oとなるので、位数2のねじれ点である。

4.射影平面上の楕円曲線[2001/04/29追加]

楕円曲線の無限遠点を通常の点と対等に取り扱うためには、射影平面
    P²={[a:b:c]:(a,b,c)!=(0,0,0)}/～
    ただし、[a:b:c]～[a':b':c']は、あるt!=0が存在して、a=ta',b=tb',c=tc'となることと定義する。
上で考えると良い。
(1)を同次化して、
  y²z=x³+ax²z+bxz²+cz³   ---- (4)
を考える。(4)上にある(射影平面上の)点[x:y:z]が無限遠点でなければ、z!=0であり、(1)上にある(平面上の)点(x/z,y/z)に対応する。
[0:1:0]はP²上の(y軸方向の)無限遠点であるが、[0:-1:0]と同一の点である。
また、[1:0:0]は[0:1:0]とは異なる(x軸方向の)無限遠点である。同様に、[1:1:0]は直線y=x方向の無限遠点である。

5.有限体上の楕円曲線

楕円曲線Cを有限体F_q上の曲線と考える。つまり、x,yをF_qの元とする。ただし、qはFの位数であり、素数pまたは素数pの巾p^mである。
この場合でも、楕円曲線上の点P(x,y)について、-,*,+の演算を同様に定義することができる。 x,yの演算は、F_qの演算(mod qの演算)とする。

6.楕円曲線を使った素因数分解[Lenstraの方法]

合成数mに対して、有限環F_m(+,-,*演算をmod mで行なう)を考える。F_mを体と見なして/の演算をすることにより、F_m上の非特異楕円曲線Cについて、その曲線上の点P(x,y)のk倍点を計算することができる。
今、mのある素因数pに対して、p-1が小さい素数の小さい巾の積となっているとする。F_p上の楕円曲線上のP(x,y)の集合C(F_p)を考えると、C(F_p)の元の個数#C(F_p)がたまたまkを割り切るならば、kP=Oとなる。よって、点Pのk倍点の計算は途中で失敗するが、その過程でmの素因数が得られる。
k倍点の計算に成功したら、特に何も言えないので、別のkまたは別の点P(x,y)または別の楕円曲線Cについて、再度、計算する。
例えば、kは、十分大きな数nに対して、k=lcm{1,2,...,n}とする。
ここでは、単純な点(2,1),(3,1)などを通る楕円曲線
    y²=x³+bx+c
を使う。ただし、
    c=-7-2b  点(2,1)を通る場合,
    c=-26-3b  点(3,1)を通る場合
とする。
Pのk倍点kPの計算では、2P,2²P,2³P,...を順に計算し, kの２進数表示に従って、例えば、13P=P+2²P+2³Pのように加算して求める。

7.プログラムについて

数年前から楕円曲線について興味を持ち、その応用である暗号アルゴリズムや素因数分解についても調べている時に、その原理を理解するために作成した。
最初に作成したのはCommon LISP版であり、bignumを標準で持っているので、作成しやすかった。コンパイルすることにより、高速に実行できる。
2001年になって、rubyもbignumを持っていることを知り、このプログラムを移植した。rubyはインタプリタであり、実行速度はGNU Common LISPより少し落ちるが、使用メモリも小さく十分に使えることがわかった。

[2021.04.22追記]
２倍点公式が誤っていたので、修正した。

[参考文献]

[1]Joseph H.Silverman, John Tate(著), 足立恒雄, 木田雅成, 小松啓一, 田谷久雄(訳), "楕円曲線論入門", シュプリンガー・フェアラーク東京, 1995, ISBN4-431-70683-6, {3900円}.
[2]足立恒雄, "フェルマーの大定理が解けた！", 講談社, BLUE BACKS B-1074, 1995, ISBN4-06-257074-2, {740円}.
[3]長尾孝一, "rankの高い楕円曲線の構成法について", p1-2.
[4]三島久典,数学者の密室--楕円曲線上の有理点、円分数の素因数分解について、とても参考になる.

Last Update: 2021.04.24

H.Nakao