元祖ワシ的日記

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

の形になかなか持ち込めないのがその要因です。

 

そこでちょっと工夫をします。

$\mod{p}$において平方非剰余の数$T$を1つ選びその平方根があると仮定してそれを$\sqrt{T}$と表すことにします。$T$は平方剰余ですから$T^{\frac{p-1}{2}}= -1 \pmod{p}$が成立します。

 

したがって

 

\[
\sqrt{T}^{p}= T^{\frac{p-1}{2}}\sqrt{T} = -\sqrt{T}
\]

 

さて、

\[
x+y\sqrt{T}
\]

 

と表すことができる数を考えます。xの選び方はp通りyの選び方はp通りですから$p^2$通りの組み合わせがあります。

 

このとき

 

\[
(x+y\sqrt{T})^p
\]

 

を考えます。上記の式は二項展開をすると

 

\[
x^p + p(\cdots) +y^p\sqrt{T}^p
\]

 

となりますが。$x^p$と$\sqrt{T}^p$以外の項には全て$p$が掛けられているので0と見なすことができます。一方フェルマーの小定理より$x^p=x, y^p=y$ですから結局

 

\[
(x+y\sqrt{T})^p = (x-y\sqrt{T})
\]
 

です。($p$乗すると共役な元になる）よって

 

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

となり$\sqrt{T}$が消えることになります。そこで

\[
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$は非平方剰余であることがわかります。よって
\[
(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}
\]

 

です。

余談）
この考えは有限体の理論によって導き出されます