元祖ワシ的日記

3n+1型の素数pについて x^2 + 3y^2 = p となる整数を求めるアルゴリズムのメモ。解があることの証明は結構面倒なんで略します。

そもそも x^2 + 3y^2 <=p なる数は有限なのだから、全ての数について調べていけば解は見つかるわけですが、pが巨大な数になると探索は非常に困難になります。そこで、このエントリではpが巨大な数でも比較的少ない計算量で求める方法を紹介します。

基本的な手法としては4n+1型の素数についての平方和 x^2 + y^2 = p の解を求めるのと同じです。

流れ

x^2 + 3y^2 = N p --(1)

となるNを探します。そこからより小さいNを探し最終的にNを1にすることで求めます。(1)式は x, yの範囲として

-p/2 < x < p/2
-p/2 < y < p/2

と出来ることに注意します。(もし一つでも解が見つかれば x = x % p, y = y % pとすればよいのです。

x^2 + 3y^2 < (p/2)^2 + 3(p/2)^2 < p^2 より

N p < p^2

すなわち

N < p

となるようにNを選べることに注意します。

アルゴリズムその1

ここで次の事実を用います。

Nもまた u^2 + 3v^2 の形に書くことができる。

証明は結構面倒なので略します。

よって(1)式は

x^2 + 3y^2 = (u^2 + 3v^2) p --(2)

と書き直せます。このような u, vを見つけることができれば(2)式は

p = (x^2 + 3y^2) / (u^2 + 3v^2)

= (x + √-3y)(x - √-3y) / (u + √-3v)(u - √-3v)

と書き直されます。（いきなり平方根とか虚数とか出てくるけど気にしない）。ここで次の事実を用います。

(x + √-3y) / (u + √-3v)

または

(x + √-3y) / (u - √-3v)

のどちらかは割りきれる。

証明は結構面倒なので略します。

ただこのやり方はpを分解するのに、Nが現れ、しかもそのNを分解するというのは本末転倒のように思えますが、実際にはNの素因数は3n+1型の素数または平方数しか現れません。さらに後述するように最初のx, yを選べば平方数を含まないようにすることもできます。また x, yの選び方から N < p となるので、Nの素因数分解が容易に出来るのであればpに比べて小さい数の分解が出来ればよく、結構高速に求めることができます。各素因子の分解についても同じように考えていけばよいのです。

ただ、pが大きな数の場合、Nも大きくなる傾向があり、探索が困難になることが考えられまs.そこで、素因数分解をしなくてもよいアルゴリズムを紹介します。

アルゴリズムその2

次のような数を探します

t^2 + 3s^2 = M N  --(3)

このような数はもうわかっていて、(1)のx, yがまさにそれです。ここで(1)同様 t, sは範囲として -N/2 から N/2の間に収めることが出来ることに注意します。（すなわち t = x % N, s = y % N　とすればよいのです）

(1)式の両辺に(3)式の両辺 を掛ければ

(x^2 + 3y^2)(t^2 + 3s^2) = M N^2 p

左辺 = (x + √-3y)(x - √-3y) (t + √-3s)(t - √-3s)
= (x + √-3y)(t - √-3s)(x - √-3y)(t + √-3s)
= {xt + 3ys  + √-3(-xs + yt)}{xt + 3ys -√-3(-xs + yt)}
= (xt + 3ys)^2 + 3(-xs + yt)^2

ところで -xs + yt = 0 (mod N)です。故に (-xs + yt)はNで割りきれます。右辺はN^2で割りきれるから等式が成立するには (xt + 3ys)^2もNで割りきれないといけません。つまり、

x' = (xt + 3ys)/N
y' = (-xs + yt)/N

はどちらも整数です。よって

x'^2 + 3y'^2 = M p

となります。t, sの値の取り方から M<Nとなりますからより小さいMを見つけることが出来ました。以下これを繰り返せばMは最終的に1にすることができます。

最初のx, yの求め方

最後に(1)式をみたすx, yの探し方を紹介します。これには1の三乗根がw必要になります。これは原始根が分かっていれば簡単にわかります。

pの原始根をeとすれば pは 3n+1型だから体Kpにおいて、

w = e^n

とすればwは1の三乗根です。これより

(w - w^2)^2 = -3 (mod P)

となりますから(w^3=1に注意して計算してみるとよい）

x = (w - w^2)
y = 1

とすれば

x^2 + 3y^2 = 0 (mod P)

を満たすから

x^2 + 3y^2 = N P

なるNが見つかったことになります。

しかし三乗根を見つけるのに原始根を探すというのはいささか面倒です。これを解決するもっとシンプルな解法があります。適当な数をランダムに選びn乗すれば2/3の確率で１の三乗根になります。10個もトライすれば見つかるでしょう。