元祖ワシ的日記

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$ですが次のような性質を持っています。

• $\omega^2$を乗ずると2段目のノードに対して左右に移動する
• $\omega^4$を乗ずると3段目のノードに対して左右に移動する
• $\cdots$
  

この性質を利用して$\omega^2(=18)$を42に乗じて(-20になる)そのノードを右側のツリーの同じ場所におきます。そしてそこからまた冪冪でルートに戻っていきます。
このルートの中に求めるノードがあればそれが答えです。残念ながら今回もみつからないので$\omega^4$を乗じます。そうすると-27が無事見つかりました。これから答えが求まります。





最後に32乗してはじめて1になる数の見つけかたですが、これは平方非剰余な数を3乗すれば求めるものになります。平方非剰余な数は全体の半数ですからランダムに選んで$(p-1)/2$乗して判定することができます。

この方法は運が悪いと沢山計算をする必要がありますが木の高さは $s$ですから最悪でも$s^2$くらいのオーダーの計算量になります。
一方葉は$2^s$のオーダでこれを全部計算するのはsが大きくなるととんでもない数になります。$s$が小さいときは非効率ですが大きくなるにつれて優位性が増すと思われます。