読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

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

mod 平方根

整数論

素数 mod p で x^2=a となる x を見つけるアルゴリズムです。Cipolla のアルゴリズムというのを紹介します。

Cipolla's algorithm - Wikipedia

前提知識

基本的に法は奇素数で考える。

平方剰余
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 平方剰余 平方非剰余
平方剰余 平方剰余 平方非剰余
平方非剰余 平方非剰余 平方剰余

アルゴリズムの流れ

b^2-a が平方非剰余となるような b を持ってくる。これは線形探索してもすぐに見つかる。というのも平方剰余の個数と平方非剰余の個数は半々であるため。

\mathbb{F}_p\sqrt{b^2-a} を添加した体を用いると、(b+\sqrt{b^2-a})^{(p+1)/2} \in \mathbb{F}_pが解になる。実際の計算は繰り返し二乗法でできる。

体の拡大というのに馴染みがないかもしれないが、実数体虚数単位 i を追加して複素数体を作るとか、二次体とかその辺の話。

b を見つけるパートの計算量がなぞだが、50% の確率で見つかるだろうから実質 O(\log p) だろう。どうでもいいとは思うが、mod 2 のときは別途処理すること。

\mathbb{F}_p上の2次方程式なので、ほとんどのケースで解は 2 つ出てくる。しかし 1 つ見つければもう片方は -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 である。