元祖ワシ的日記

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