Integral Points on Conic Curve: x^2-xy+y^2=63812593012478171313181
[2001.06.02]x2-xy+y2=63812593012478171313181の整点
■Q[\rho]上での有理素数p=3n+1の素因数分解
Euclid整域Q[\rho]上で、有理素数p=3n+1の素因数分解を考察する。
(a+b\rho)(a+b\rho2)=p --------(1)
となる有理整数(a,b)が存在し、a+b\rho,a+b\rho2は、Q[\rho]の素数である。pが与えられたとき、(a,b)を効率良く求めることができる。
(1)より、Q[\rho]の代数的整数a+b\rhoは、pの約数である。
もし、k2≡ -3 (mod p)となる有理整数kを求めることができれば、
(k-1-2\rho)(k-1-2\rho2)=k2+3 ≡ 0 (mod p) --------(2)
であり、a+b\rhoは素数なので、Q[\rho]の素因数分解の一意性から、a+b\rhoは(k-1-2\rho)または(k-1-2\rho2)の約数である。
よって、Q[\rho]上でpおよび(k-1-2\rho)のgcdを(Euclidの互除法で)計算すると、a+b\rhoまたはその同伴数(associate)のどれかを得ることができる。
最後に、与えられた(a,p)に対して、x2≡ a (mod p)となる有理整数xを求める方法は、参考文献[2]によると、以下のアルゴリズムで実現できる。
■mod pでのaの平方根、つまりx2≡ a (mod p)なるxを求める。
- 乱数nでかつmod pで平方非剰余なるもの,つまり,(n/p)= -1なるnを選択する。
ただし、(・/・)は平方剰余記号とする。
- p-1=2eqを満たすe,q(奇数)を計算する。
- y:=nq(mod p), r:=e, x:=a(q-1)/2 (mod p)
- b:=ax2(mod p), x:=ax (mod p)
- while b \not\equiv 1 (mod p) do:
- m:=min{m >=0 | b2m≡ 1 (mod p)}
- t:=yr-m-1 (mod p), y:=t2 (mod p), r:=m
- x:=xt (mod p), b:=by (mod p).
- return x.
■x2-xy+y2=63812593012478171313181の整点を求める。
有理素数63812593012478171313181 ≡ 1(mod 3)をQ[\rho]上で素因数分解することに帰着する。
上記の２次曲線上の整点(x,y)を求めるプログラムを作成して、実行すると、このようになる。
その整点は全部で以下の6個である。
(-251320726401,-253882874381),(251320726401,253882874381),
(253882874381,2562147980),(-253882874381,-2562147980),
(2562147980,-251320726401),(-2562147980,251320726401).
[参考文献]
- [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: 2005.08.20 |
| H.Nakao |