自分メモ

2010年09月10日(金)

ひらめいたのでメモしておく。

3n+1型の素数Pは x^2 + 3y^2 = P と表すことができる。その証明は代数学の環論でされるわけですが、数学者というのは証明しちゃったあと具体的にそれを求めるアルゴリズムをちゃんと説明してくれないから困るわけで。

このやり方をずーっと考えていました。

自明なやり方は1..P-1までの数全てについて、試してみる。所詮数は有限だ。しかし、これは、Pが大きくなると数が多くなり結構大変です。

オイラが出した手法は次の通り。

step 1) x^2 + 3 = 0 ( mod p)

の解を解く。つまり x^2 + 3 がpで割り切れるのだから、x^2 + 3 = npである。(nは整数)

step 2) step1の式は

x^2 + 3y^2 = np でy = 1としたものである。ここから、頑張ってより小さい x, y, nを探してゆき、最終的に nを１にする。

この二本立て。

さて、アルゴリズム的には STEP2のほうがすぐ思い付いた。

これは二次体の整数 K(√-3)を考えれよい。この世界では左辺は

(x-y√-3)(x+y√-3) = np と因数分解できる。

左辺は共役でn, pで割り切れないから、右辺のnもpも共役な積に分解されるはずである。

ここで証明をはしょって結論だけかけば、nは 3n+1の形の素数((a-b√-3)(a+b√-3)と分解可)、3(=√-3*√-3)、4(=(1+√-3)(1-√-3))、の積である。

故にこれらの因数で左辺の２項のどちらかが割り切れる。 (例えばnが素因数として 4を含むなら (x-y√-3), (x+y√-3)のどちらかが(1+√-3)で割り切れるはずだ。

このようにして、どんどん分解していけば最終的に求める式が求まる。

で、問題のSTEP1ですが、こちらはこうやる

x^2 = -3 ( mod p)

を求める。

ところで、 3n+1の素数Pの原始根をeとすれば n=P-1乗すると1になるのだが、これは3で割り切れるから、mod Pでは1の三乗根がある。これらの数は nを三等分したところ、すなわち

e^(n/3)

e^(2n/3)

である。これをωとω^2とおけば

ω + ω^2 = -1

に注意してその差の自乗を計算すると

(ω - ω^2)^2 = (ω^2 + ω - 2ω^3) = -3

故にω - ω^2 が答えである。

(ω - ω^2)^2はいわゆる判別式。

ω + ω^2 = -1となるのは

ωはx^3 - 1の根であり、自明な根１をくりだしてやれば

x^3 - 1 = (x-1)(x^2 + x + 1)

第二項が０になるはずだからω^2 + ω +1 = 0

このあたり円分多項式とかなり関連があるわけで、このようにリンクするのがまた面白い。

例素数2011を考える。原始根は3である

ω= 3^670 = 205 ω^2 = 3^1340 = 1805

故にその差 1600 = -411 (mod 2011)がSTEP１の解。実際

411^2 + 3 = 84 * 2011

である。 84は 4*3*7と因数分解できる。7は3n+1型だから、(x+y√-3)(x-y√-3)の形に表せる。4も3も同様。実際に割って行くと

44^2 + 3*5^2 == 2011

を得る。

コメント一覧

> (x-y√-3)(x-y√-3) = np と因数分解できる。これは， (x-y√-3)(x+y√-3) = np と因数分解できる。ではないのか？ほかにも，(a-b)(a+b)となるべきものが (a-b)(a-b)になっているものがある気がする．

するどい指摘ありがとうございました。早速直しておきました。