元祖ワシ的日記

$$x^2=a(\mathrm{mod}p)$$

の解がわかると

$$x^2=a(\mathrm{mod}{p}^2)$$

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

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

$$x^2-a=up$$

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

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

両辺を二乗すれば

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

$$\begin{array}{r}((x^2+a)-2x\sqrt{a})((x^2+a)+2x\sqrt{a})=u^2{p}^2\end{array}$$

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

 $$\begin{array}{r}(\frac{x^2+a}{2x}-\sqrt{a})(\frac{x^2+a}{2x}+\sqrt{a})=\frac{u^2{p}^2}{4x^2}\end{array}$$

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

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

$$\begin{array}{rl}(8-\sqrt{7})(8+\sqrt{7})& =3\cdot 19\\ (71-16\sqrt{7})(71+16\sqrt{7})& =3^2\cdot {19}^2\end{array}$$

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

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

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