元祖ワシ的日記

一つ前のエントリでは

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことが出来たのでした。同じ考え方で任意の$p^k$について次のようにして求めることが出来ます。

\[
(x-\sqrt{a})^k
\]
を計算して
$\sqrt{a}$の係数が$\pmod{p^k}$で1になるように逆数を乗じればokです。

$\sqrt{a}$の係数が$p$で割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
$(2u)^{k-1}$に$\mod{p}$で等しくなります。つまり$u^2=a\pmod{p}$としたとき

\[
(u_{k}-v_{k}\sqrt{a})
=(u-\sqrt{a})^k
\]
とすると

\[
v_k=(2u)^{k-1}\pmod{p}
\]
となります。よって$v_k$は$p$と互いに素で、逆数が存在することになり解を求めることが出来ます。

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことができます。その手順について解説します。

$x^2 = a \pmod{p}$の解があるということは

\[
x^2 - a = up
\]

なる$u$があるということです。左辺は次のように変形することができます。

\[
(x-\sqrt{a})(x+\sqrt{a})=up
\]

両辺を二乗すれば

\[
(x-\sqrt{a})^2(x+\sqrt{a})^2=u^2p^2
\]
これより

\[
 \begin{aligned}
((x^2+a)-2x\sqrt{a})((x^2+a)+2x\sqrt{a})=u^2p^2\\
\end{aligned}
\]

を得るので$2x$で各係数を割れば

 \[
\begin{aligned}
\left(\frac{x^2+a}{2x}-\sqrt{a}\right)
\left(\frac{x^2+a}{2x}+\sqrt{a}\right)=\frac{u^2p^2}{4x^2}\\
\end{aligned}
\]

となり$\frac{x^2+a}{2x}$が解になります。最後の$2x$で割るというところが微妙ですが、これはここから$p^2$での剰余を考えて演算をするということで解決できます。

例
\[
8^2-7=3\cdot 19\\
\]
が既知とします。

\[
\begin{aligned}
(8-\sqrt{7})(8+\sqrt{7})&=3\cdot 19\\
(71-16\sqrt{7})(71+16\sqrt{7})&=3^2\cdot 19^2\\

\end{aligned}
\]

ここで
\[
16 x = 1\ \pmod{19^2}
\]
なる数を探します。すると$158$であることがわかるので左辺の各項に乗じて$19^2$での剰余を求めると

\[
(27-\sqrt{7})(27+\sqrt{7})=0  \pmod{19^2}
\]
を得ることができます。

注)
$2x$が$p$と互いに素であることが重要です。$x$はあきらかに$p$と素ですが2を乗じているので$p$は奇素数でなければなりません。

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$が小さいときは非効率ですが大きくなるにつれて優位性が増すと思われます。