ほぼ雑記的メモ
タイトルにも数式を書けるようににしてみました。
$\log{i}$は$e$を何乗かして$i$になる数であるから
\[\log{i}=\frac{\pi}{2}i\]
（正確にはそれに$2\pi i$足したり引いたりした数もだがとりあえずそれはおいとく）
\[i^i = e^{i\log{i}} = e^{-\frac{\pi}{2}} = 0.207879576350761908\cdots\]
8N+1の素数について、もう一つ別の考え方を解説します。多分Tonelli–Shanksのアルゴリズムと同じ考えに基づくものと思われます。$p-1=2^s t$(ただし$t$は奇数)とおきます。すると任意の$x$に対して\[(x^t)^{2^s} = 1\]ですから$x^t$は1の$2^t$乗根です。例えば97を考えると\[96 = 2^5\cdot 3\]ですから $x^3$は1の32乗根です。一般的に1の32乗根は32個あり、そのうち16個が32乗してはじめて1になる数です。ある数$\omega$が32乗して初めて1になる数とすれば$\omega^3, \omega^5, \cdots, \omega^31$もまた32乗根してはじめて1になる数です。よって1つそのような数を見つければ他の数は自然と見つかることになります。（余談ながらその逆数$\omega^{-1}, \omega^{-3},\cdots, \omega^{-31}$も然りです） $\omega$を32乗して初めて1になる数（例えば42）としてその数を2乗、4乗としてこれを木の形にしてみます。（下図参照）空白になっているところにも$2$の冪乗根があるはずですがそれは何かわからないので空欄にしておきます。また平方根についてはaが平方根の1つなら-aもまた平方根ですので剰余を0から95ではなく-48から47までの間になるように書いています。木の葉のほうから辿れば42 → 18 → 33 → 22 → -1
です。この中に$a^3$があれば答えは簡単です。例えば$a$が$47$とすれば、$a^3=33$ですから、1つ下の$18$を使って\[a^3 = 33 = 18^2\]これより両辺に$a$をかけて\[a^4 = 18^2a\]を得て\[(a^2 18^{-1})^2 = a\]が答えになります。$18$の逆数 ($18 x =1$なる数)が出てきますがこれは普通に求めてもいいし、そもそも$18^{16-1}=27$が逆数なのでそれを利用しても簡単に求まります。答えとしては$-12$が得られます。実際$-12^2=47$です。
そうではない場合（例えば$11$）を探す場合は次のようにします。$11^3=-27$です。$-27$を冪冪で累乗していくと\[\begin{eqnarray}(-27)^2 = -47\\(-47)^2 = -22\end{eqnarray}\]となり、ここで$-22$が出ます。$-22$はツリーのルートのすぐ右側にあるので、この数はツリーの右側にあることがわかります。ところで$\omega$ですが次のような性質を持っています。
$p$を素数とし、$q=p^n$とする。有限体$F_p$上の多項式$X^q-X$は$d$を$n$の約数とすると$d$次の約数既約多項式全てを因子に持つ。
証明はそんなに難しくないのでまたの機会にでもここに書きます。とりあえず、例を上げます（例が多いブログなもので・・・）
例1) $F_2$上の$X^{4} - X$の因数分解を考えます。$n=2$です。よって1次式と2次式の分解できます。実際計算してみると \(\begin{eqnarray*} X^{4} - X = X(X+1)(X^{2} + X + 1) \end{eqnarray*}\)
となります。この式はこれ以上分解するのは不可能です。
例2) $F_2$上の $X^{8} - X$の因数分解を考えます。$n=3$です。 この式は3の約数である1次と3次の既約多項式を因子に持ちます。実際計算してみると
\(\begin{eqnarray*} X^{8} - X &=& X(X-1)(X^6 + X^5 + \cdots + 1)\\ &=& X(X-1)(X^3 + X + 1)(X^3 + X^2 + 1) \end{eqnarray*}\)
例3) $F_2$における$X^{16} - X$の因数分解を考えます。$n=4$です。 よって$n$の約数である既約4次式、2次式、1次式を因子にもちます。実際計算してみると、
\(\begin{eqnarray*} X^{16} - X &=& X(X-1)(X^{2} + X + 1)(X^{12} + X^{11} + \cdots + 1)\\ &=& X(X-1)(X^{2} + X + 1)(X^4 +X +1)(X^4 +X^3 +1)(X^4 +X^3 +X^2 +X +1) \end{eqnarray*} \)
以上なんとなく感覚がつかめていただいたでしょうか？２の冪以外の例はまた別の機会にここに書きます。
さて、ここから$F_q$における$n$次の既約多項式の個数を求めます。
$X^q-X$において$n$次の既約多項式の根を全て掛け合わせたものの次数を$\nu(n)$とします。先ほどの例で言えば
\(\begin{eqnarray*} \nu(1)&=& 2\\ \nu(2) &=& 2\\ \nu(3) &=& 6\\ \nu(4) &=& 12\\ \end{eqnarray*}\) です。この先ですが
\(\begin{eqnarray*} \nu(5) &=& 30\\ \nu(6)&=& 54\\ \end{eqnarray*}\)
と続きます。
さて、$F_q$には$n$の約数である$d$次の既約多項式がすべて存在します。それらの次数を足し合わせれば当然$q$になります。よって、
\(\begin{eqnarray*} \sum_{d|n}{\nu(d)} = q = p^n \end{eqnarray*}\)
が成立します。ここからメビウスの反転公式を使って
\(\begin{eqnarray*} \nu(d) = \sum_{d|n}{\mu\left(\frac{n}{d}\right)p^d} \end{eqnarray*}\)
となります。$\nu(d) / n$が$n$次式の個数になるので
\(\begin{eqnarray*} \frac{1}{n}\sum_{d|n}{\mu\left(\frac{n}{d}\right)p^d} \end{eqnarray*}\)
が求める個数になります。
wikipediaより
オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）は各正の整数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。慣例的に φ(n) と表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。
簡単にするためまず$n$の素因数分解を$p_1 p_2 p_3 \cdots p_n$とし因子に平方数を含まないとします。 (つまり素数 $p_1, p_2, p_3, \cdots$の羃は1)
$1$から$n$のうち$p_1$の倍数の数が $n / p_1$個あり、 $p_2$の倍数が $n / p_2$あり……ということでこれらの数を$n$から引きます。しかし、これでは $p_1 p_2$など2つの素数の積の数を2回引いてしまうのでそれらを足します。しかし、これでは $p_1 p_2 p_3$のような3つの素数の積になってる数を足しすぎてしまうのでそれらをまた引きます……と考えていけば……
平方数を含む場合ですが例えば $12$のときを考えれば$2$の倍数を除去したときに12の因数である$4$の倍数は既に除去されています。つまり、平方因子をもつ約数は考慮しなくてもよいのです。（つまり、素因数が何種類あるか？が重要）これはそのまま一般に拡張出来ます。実際上記の式は $n$の素因数分解を$p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$と分解される場合でも成立します。
$n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_n^{e_n}$の素因数をそれぞれの項に配分していけば
なお、上記の式はメビウス関数を使えば \begin{eqnarray} \phi(n) = \sum_{d|n}\mu({d}){\frac{n}{d}} \end{eqnarray} とも表わすことができます。メビウス関数$\mu({n})$は
ここからメビウスの反転公式を使って
以上Mathjaxのリハビリでした
相当前にエントリに書いた$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$を意味する。