元祖ワシ的日記

相当前にエントリに書いた$4n+1$の素数を平方の和にするアルゴリズムですがガウス整数を使ったもっとスマートな解法を紹介します。

まず前回同様 $p$を$4n+1$の素数として $$A^2 + 1 = 0 (\mod p)$$ なる$A$を求めます。

$$A^2 + 1 = k p$$ です。

左辺はガウス整数を使うとさらに因数分解できて $$(A + i)(A - i) = k p$$ となります。

ここでガウス整数は通常の整数と同様、素因数分解等素数の性質があることを踏まえて等式を見てみます。

$p$はあきらかに$A+i$および$A-i$を割きりません。ということは$p$はガウス整数の世界ではさらなる素数に分解できることを意味します。すなわち最大公約数$(A+i, p)$は1ではなく、$x+iy$の形をしたガウス整数となります。

$(A+i, p) = x + iy$ ならば共役の関係から $(A-i, p) = x - iy$がまた成立します。 一方$(x + iy)(x - iy)$を考えるとこれは有理整数$x^2+y^2$となりこれは$p$を割り切らないといけませんが、 $p$は素数ですから結局これは$p$に等しく$p = x^2 + y^2$となります。

つまり$p$と$A+i$の最大公約数を求めればそこから解は自動的に求まることになります。

最大公約数はガウス整数の世界でもユークリッドの互除法で簡単に求めることができます。

例として、素数$p=120710677$を二つの和にしてみます

$$46505545^2 + 1^2 = 17916938 \times 120710677$$

ですから最初は$46505545+i$と$120710677$の最大公約数を求めればよいことになります。

$$A_0 = 46505545+i\\ B_0 = 120710677$$ とします。

ノルムを比較すると$|A_0| < |B_0|$で $A_0 = 3 * |B_0| + ...$ ですから最初の計算では $A_1 = A_0, B_1 = B_0 - 3A_0$とすればよいことがわかります。 実際計算してみると $$A_1 = 46505545+i\\ B_1 = -18805958-3i$$ となります。以下同様にして計算していくと

$$\begin{align} A_2&=&8893629-5i, B_2&=&-18805958-3i\\ A_3&=&8893629-5i, B_3&=&-1018700-13i\\ A_4&=&-274671-122i, B_4&=&-1018700-13i\\ A_5&=&-274671-122i, B_5&=&79984+475i\\ A_6&=&-34719+1303i, B_6&=&79984+475i\\ A_7&=&-34719+1303i, B_7&=&10546+3081i \end{align}$$ ここで$B_7$が求める答えになります。実際 $$10546^2+3081^2 = 120710677$$ です

注意

ユークリッドの互除法ではノルムの大きいほうをノルムの小さいほうで割ってその余りに置き換えるという手順を踏むのですが、それは以下のようにして求めます。

$a+ib$を$c+id$で割る場合は $$\frac{a+ib}{c+id} = \frac{(a+ib)(c-id)}{c^2+d^2} = \frac{ac+bd}{c^2+d^2} + \frac{bc-ad}{c^2+d^2}i$$ ここで、有理数 $$\frac{ac+bd}{c^2+d^2}, \frac{bc-ad}{c^2+d^2}$$ に最も近い整数を$n$, $m$とすれば $$(a+ib) = (n+im)(c+id) + (r+is)$$ と書いたときに、$r+is$のノルムは$c+id$より小さくなります。よって$r+is$を余りとみなして計算を進めていくことができます。

別の考察

この例では$(A+i, p)$を考えましたが、$(A+i, k)$を考えても同様に計算をすることができることがわかります。

この場合最大公約数を求めなくても以下のように計算をすることができます。

$$a^2 + b^2 = 0 (\mod k)$$ であることを考えると $a' = a(\mod k), b' = b(\mod k)$とおけば $$a'^2 + b'^2 = 0 (\mod k)$$ もまた成立します。つまり$a'^2 + b'^2$は$k$を割りきります。つまり $$\frac{(a+ib)(a-ib)}{(a'+ib')(a'-ib')} = \frac{k}{a'^2 + b'^2}p = k'p$$ が成立します。右辺は整数ですから左辺は共役なガウス整数の積にならなければなりません。 よって $$\frac{a+ib}{a'+ib'}または\frac{a+ib}{a'-ib'}$$ のどちらかがガウス整数になります。ここで $$\begin{align} -k/2 &<& a' &<& k/2\\ -k/2 &<& b' &<& k/2 \end{align}$$ なるように a', b'を選べば kより小さい k'が見つかることになります。 この手順を繰替えせば kより始めていつかは1になるので求める解を見付けることができます。

これが前回解説したアルゴリズムと同じものになります。

さらりと流した部分の補足

有理整数がガウス整数の積で表わされる必要条件は共役の因子を含むことである。

ガウス整数をそれぞれ $a+ib$と$c+id$とする。$c\ne 0$, $d\ne 0$, $(a,b)=1, (c,d)=1$と仮定して問題ない。 なぜならもし$(a,b)=k > 1$ならば$a' = a/k, b' = b/k$として $k(a' + ib')(c+id)$を考えればよいからである。 $$(a+ib)(c+id) = (ac-bd) + i(ad+bc)$$ が有理整数なのだから$ad+bc=0$すなわち $ad=-bc$が成立する。 よって、$a$と$b$と互いに素だから$c$が$d$を割り切りかつ$d$が$c$を割きらなければならないが、 これは $c=d$または$c=-d$を意味する。$c=d$とすれば$a=-b$であり$c=-d$とすれば $a=b$である。 いずれにしても共役の因子を含まなくてはならない。

有理整数が共役の数の積で表わされているのなら、その数はガウス整数でなければならない。

$a/b$および$c/d$を考える。$(a,b)=1, (c,d)=1$と仮定して問題ない $$(\frac{a}{b}+i\frac{c}{d})(\frac{a}{b}-i\frac{c}{d}) = \frac{a^2c^2}{b^2d^2}$$ から $$b^2d^2 = 1$$ これは$b=\pm 1, d=\pm 1$を意味する。