pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

mod 平方根

素数 mod p で x^2=a となる x を見つけるアルゴリズムです。Cipolla のアルゴリズムというのを紹介します。平方剰余に詳しくない方はまず補足を読んで下さい。

Cipolla's algorithm - Wikipedia

アルゴリズム

b^2-a が平方非剰余となるような b をどれでも良いので一つ見つける。\(\mathbb{F}_p\)の半数が平方非剰余であるため、線形探索をしても確率的にすぐに見つかる。

\mathbb{F}_p(\sqrt{b^2-a}) に拡大すると解の公式が得られ、(b+\sqrt{b^2-a})^{(p+1)/2} \in \mathbb{F}_p が解になる。これは繰り返し二乗法により高速に計算できる。

\mathbb{F}_p上の二次方程式なので、解 \(x\) をひとつ見つければ他の解は -x である。

証明

補題 D が平方非剰余ならば (\sqrt{D})^p=-\sqrt{D}

オイラーの基準より D^{(p-1)/2}=-1 が成り立つため、(\sqrt{D})^{p-1}=-1 である。

定理 (b+\sqrt{b^2-a})^{p+1}=a

二項定理により (b+\sqrt{b^2-a})^{p}=b^p+(\sqrt{b^2-a})^p=b-\sqrt{b^2-a} である。

定理 (b+\sqrt{b^2-a})^{(p+1)/2} \in \mathbb{F}_p

(u+v\sqrt{D})^2 \in \mathbb{F}_pが平方剰余のとき v=0 を示せば定理を示したことになる。証明は背理法に基づく。(u+v\sqrt{D})^2 = u^2+v^2D+2uv\sqrt{D} \in \mathbb{F}_p なので  u=0 または  v=0 である。u=0,v\neq 0 と仮定すると v^2D が平方剰余ということになるが v^2D は平方非剰余であるため矛盾している。つまり  v=0 である。


補足

法 \( p \) は奇素数とする。

平方剰余
aが平方剰余であるとは、 \bmod px^2=a となる x が存在することを意味する。平方剰余でないことを平方非剰余と呼ぶ。
ルジャンドル記号
\displaystyle \left( \frac{a}{p} \right)a が平方剰余のとき 1、平方非剰余のとき -1 となる関数。
オイラーの基準
\displaystyle \left( \frac{a}{p} \right)=a^{(p-1)/2} \bmod p競技プログラミングで平方剰余判定をするならこれが楽。
ルジャンドル記号の基本性質
a,bp の倍数でないのであれば、\displaystyle \left( \frac{ab}{p} \right)=\left( \frac{a}{p} \right)\left( \frac{b}{p} \right)
平方剰余の積
積に関して以下のことが分かる。
\times 平方剰余 平方非剰余
平方剰余 平方剰余 平方非剰余
平方非剰余 平方非剰余 平方剰余