楕円曲線上の有限位数の有理点を求める

J.H.Silverman and J.Tateの 楕円曲線論入門 の2章に以下のような定理がある．

問題2.12では，さまざまな3次曲線に対して，有限位数の有理点をすべて求め，それらの点で生成される群の構造を決定せよという問題がある．

一方で，有限位数の有理点であることを示すためには，原点（無限遠点）に到達するまで、3次曲線上の群演算を繰り返さなければならない．これは極めて膨大な計算が必要となる．

そこで，定理１を利用して，有限位数の有理点の候補（定理１は必要条件であるため）を抽出するために以下のようなPythonプログラムを作成した．

1. $D$の因数分解を行う
2. 点$P=(x,y)$を与えると$m=1\sim 12$で$mP$を求める．ただし，無限遠点に到達したら終了する．

      from fractions import Fraction
import collections

# 楕円曲線上の2点P,Qから、点(P+Q)を求める
def elliptic_group(a,b,c,x1,y1,x2,y2):
  if x1 == x2:
    if y1 == y2 and y1 != 0:
#      x3 = Fraction(pow(x1,4) - 2*b*pow(x1,2) - 8*c*x1 - 4*a*c + pow(b,2), pow(y1,2))
#      y3 = Fraction((3*pow(x1,2) + 2*a*x1 + b)*(x1 - x2) - 2*pow(y1,2), 2*y1)
      l = Fraction(3*pow(x1,2) + 2*a*x1 + b, 2*y1  )
    else:
      x3 = x1
      y3 = float('inf')
      return x3,y3
  else:
    l = Fraction(y2-y1,x2-x1)

  n = y1- l*x1
  x3 = l*l - a - x1 - x2
  y3 = - (l*x3 + n)
  return x3,y3

# 整数を因数分解する
def prime_factorize(n):
    a = []
    if n == 0:
      a.append(0)
    else:
      if n < 0:
        a.append(-1)
        n = -n
      while n % 2 == 0:
          a.append(2)
          n //= 2
      f = 3
      while f * f <= n:
          if n % f == 0:
              a.append(f)
              n //= f
          else:
              f += 2
      if n != 1:
          a.append(n)
    return a

# 三次関数の判別式Dを求める
def calc_D(a,b,c):
  D = -4*pow(a,3)*c + pow(a,2)*pow(b,2) + 18*a*b*c - 4*pow(b,3) - 27*pow(c,2)
  return D
    

      # y^2 = x^3 + a x^2 + b x + c の楕円曲線について
a,b,c = input("スペース込みでa,b,cを入力してください：").split(" ")
a = int(a)
b = int(b)
c = int(c)

D = calc_D(a,b,c)
print("D={}で因数分解は{}".format(D,collections.Counter(prime_factorize(D))))

bl = True
while(bl):
  x,y = input("点の整数点P =(x,y)をスペース区切りで入力：").split(" ")
  x = int(x)
  y = int(y)
  x2,y2=x,y
  i=1
  while(y2!=float('inf')):
    i+=1
    x2,y2=elliptic_group(a,b,c,x,y,x2,y2)
    print("{}P=({},{})".format(i,x2,y2))
    if(i>12):break
  bl = input("終わるならnを入力:")=="n"
  bl = not(bl)
    

このプログラムでは例えば、$y^2=x^3+4$の$D$の値は以下のように$D=-432=-2^4\times 3^3$と算出される

      スペース込みでa,b,cを入力してください：0 0 4
D=-432で因数分解はCounter({2: 4, 3: 3, -1: 1})
    

さらに，$y=0$では$x$は有理数解を持たないので，$y^2$の候補である$1,4,9,16,36,144$について$x$の有理数解を考えると，$P=(0,\pm 2)$が有限位数の有理点の候補となる．そこで，さらにこれら2点を入力すると，以下のように位数を求めることが出来た．

      
点の整数点P =(x,y)をスペース区切りで入力：0 2
2P=(0,-2)
3P=(0,inf)
終わるならnを入力:0 -2
点の整数点P =(x,y)をスペース区切りで入力：0 -2
2P=(0,2)
3P=(0,inf)
    

この2点に原点（無限遠点）を加えた3点$\{O,(0,\pm 2)\}$は3次曲線上の群演算で位数３の巡回群となる．