元祖ワシ的日記

\[
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$は奇素数でなければなりません。