Integral Points on Conic Curve: x^2-xy+y^2=63812593012478171313181

[2001.06.02]x²-xy+y²=63812593012478171313181の整点

x^2-xy+y^2=p (p=3n+1:prime)の整点を求めるプログラム(Common LISP版)

■Q[\rho]上での有理素数p=3n+1の素因数分解

Euclid整域Q[\rho]上で、有理素数p=3n+1の素因数分解を考察する。
(a+b\rho)(a+b\rho²)=p --------(1)
となる有理整数(a,b)が存在し、a+b\rho,a+b\rho²は、Q[\rho]の素数である。pが与えられたとき、(a,b)を効率良く求めることができる。

(1)より、Q[\rho]の代数的整数a+b\rhoは、pの約数である。
もし、k²≡ -3 (mod p)となる有理整数kを求めることができれば、
(k-1-2\rho)(k-1-2\rho²)=k²+3 ≡ 0 (mod p) --------(2)
であり、a+b\rhoは素数なので、Q[\rho]の素因数分解の一意性から、a+b\rhoは(k-1-2\rho)または(k-1-2\rho²)の約数である。
よって、Q[\rho]上でpおよび(k-1-2\rho)のgcdを(Euclidの互除法で)計算すると、a+b\rhoまたはその同伴数(associate)のどれかを得ることができる。

最後に、与えられた(a,p)に対して、x²≡ a (mod p)となる有理整数xを求める方法は、参考文献[2]によると、以下のアルゴリズムで実現できる。

■mod pでのaの平方根、つまりx²≡ a (mod p)なるxを求める。

乱数nでかつmod pで平方非剰余なるもの,つまり,(n/p)= -1なるnを選択する。
ただし、(・/・)は平方剰余記号とする。
p-1=2^eqを満たすe,q(奇数)を計算する。
y:=n^q(mod p), r:=e, x:=a^(q-1)/2 (mod p)
b:=ax²(mod p), x:=ax (mod p)
while b \not\equiv 1 (mod p) do:
m:=min{m >=0 | b^{2^m}≡ 1 (mod p)}
t:=y^r-m-1 (mod p), y:=t² (mod p), r:=m
x:=xt (mod p), b:=by (mod p).
return x.

■x²-xy+y²=63812593012478171313181の整点を求める。

有理素数63812593012478171313181 ≡ 1(mod 3)をQ[\rho]上で素因数分解することに帰着する。
上記の２次曲線は、x,yについて対称なので、(x,y)がその整点ならば、(y,x)もその整点である。
上記の２次曲線上の整点(x,y)を求めるプログラムを作成して、実行すると、このように、6個の整点が見つかる。
よって、上記の２次曲線の整点はこれらの6個とx,yを入れ替えた点6個、全部で12個である。

     ±(251320726401,253882874381),
     ±(253882874381,2562147980),
     ±(2562147980,-251320726401),
     ±(253882874381,251320726401),
     ±(2562147980,253882874381),
     ±(251320726401,-2562147980)

[参考文献]

[1]G.H.Hardy, E.M.Wright, "An Introduction to the Theory of Numbers 5th edition", Oxford University Press, 1979, ISBN0-19-853171-0.
[2]Ian Blake, Gadiel Seroussi, Nigel Smart, "Elliptic Curves in Cryprography", LMS 265, Cambridge University Press, p18-19, 1999, ISBN0-521-65374-6.

Last Update: 2016.11.07

H.Nakao