元祖ワシ的日記

一つ前のエントリで8N+1型以外の素数についての平方根の計算方法を解説しました。8N+1については同じような考えで求めようとしてもなかなかうまくいきません。
$$a^n = \pm a　（ただしnは偶数）$$

の形になかなか持ち込めないのがその要因です。今まで考えきた演算は$p$での剰余をもって演算するもので代数学的には$F_p$で演算と呼ばれるものです。$F_p$は$p$個の元からなる有限の集合で、その元同士に加減乗除が定義されているものです。この空間で演算をしている限りこの問題をクリアすのはどうも不可能なようです。そこで発想をちょっと変えて$F_p$ではなく$F_q$で考えることにします。$F_q$とは$F_p$の世界で既約な方程式の根を追加した体（加減乗除がうまく定義された集合）です。$F_p$は$p$個の元からなる体ですが、$F_q$は$q$個の元からなるので$F_q$と表現します。今回はちなみに$q=p^2$なので、$F_{p^2}$と記述するのが正確なのかもしれませんが、とりあえず$F_q$と表現しておきます。なんか難しいこと言ってますが発想としては簡単で$F_p$での平方根が存在しない数の平方根があると仮定してそれを追加したもの・・とゆるく考えておけばよいかと思います。

例えば有理数においても$2$の平方根は存在しませんが、仮にそれを$\sqrt{2}$と書くとすれば
$$x+y\sqrt{2}$$
という数の集合を考えることができてその集合に対して加減乗除が定義できます。例えば上記の数は二乗することが可能で二乗した結果は

$$(x^2+2y^2 )+ (2xy)\sqrt{2}$$

であってその結果もまた $x + y\sqrt{2}$の形に書けることがわかります。詳細は書きませんが割る場合も同様です。つまり$x+y\sqrt{2}$の形の集合を考えれば全ての加減乗除はその内部で閉じておりまた完結していることになります。

$F_q$もそれと同じ原理を用います。$F_p$から平方非剰余の数を$T$1つ選びその平方根があると仮定してそれを$\sqrt{T}$と表すことにし、この数を$F_p$に追加します。この集合に対して加減乗除が成立するためには
$$x+y\sqrt{T}$$ と表すことができる数全てに対して加減乗除が閉じていることを示す必要がありますが証明は割愛します。xの選び方はp通りyの選び方はp通りですからこの体は$p^2$個の元からなることになります。

 

$q=p^2$

 

とします。するとこの$F_q$に対してもフェルマーの小定理が成立して

$$x^q=x$$

が成立することが知られています。つまり$F_q$では$q$乗すると元に戻ります。ところで$F_p$では

$$x^p=x$$

が成立しました。$F_p$は$F_q$に含まれていると考えられますから、$F_q$においても$F_p$に属する元ははその位置を変えません（固定される）。しかし$F_p$に含まれない数はそうではなく、別な数に移動します。

この移動先は共役元になることが知られています。つまり

 
$$(x+y\sqrt{T})^p = (x-y\sqrt{T})$$
です。となれば$F_q$では任意の元を$p+1$乗すると

$$(x+y\sqrt{T})^{p+1} = (x+y\sqrt{T})(x-y\sqrt{T}) = x^2 -y^2 T$$

となりその数がなんであり$F_p$に属することになります。よって

$$x^2 -y^2 T=a$$
となるようにうまく$x,y$を選ぶことができれば$p+1$は偶数ですから

$$(x+y\sqrt{T})^\frac{p+1}{2}$$

がその平方根になります。

 

仮に$y$を1として探してみます。このとき

$$T= x^2 -a$$

が成立するので$x$を適当に変えてみてその値から$a$を引いたもとのが非平方剰余である数を$T$として選べば良いことになります。

例)
$p=41$とし$8$の平方根を考えます。$x$を色々変えて見ると、$5^2-8=17$は非平方剰余であることがわかります。よって$F_{1681}$で考えることにより
$$(5+\sqrt{17})^{21}$$
が答えになります。

実際計算をしてみると
$$\begin{eqnarray} (5+\sqrt{17})^2=(1+10\sqrt{17})\\ (5+\sqrt{17})^4=(20+20\sqrt{17})\\ (5+\sqrt{17})^8=(25+21\sqrt{17})\\ (5+\sqrt{17})^{16}=(4+25\sqrt{17}) \end{eqnarray}$$
ですので
$$(5+\sqrt{17})^{16}(5+\sqrt{17})^{4}(5+\sqrt{17})^{1} =34$$

となります。実際

 

\[

34^2=8\pmod{41}

\]

です。

余談）
$F_p$のような体を有限体（要素の数が有限なので）と言いますがその要素の数（位数とよぶ）は必ず$p$の冪であり、また$p$の冪の有限体は必ず存在することがわかっています。