$\bmod p$ の平方根：多項式の因数分解

素数 $p$ と整数 $a$ に対して $x^2=a \bmod p$ なる $x$ を（存在するなら）求めるアルゴリズムを紹介します。ここで用いるのはCantor–Zassenhausの多項式の素因数分解のアルゴリズムです。つまり、$$x^2-a=(x-\sqrt{a})(x+\sqrt{a}) \bmod p$$ という多項式の因数分解を求めることで $\sqrt{a} \bmod p$ を求めます。$\sqrt{a} \in \mathbb{Z}/p\mathbb{Z}$ かどうかはオイラーの基準 $$\sqrt{a} \in \mathbb{Z}/p\mathbb{Z} \Leftrightarrow a^{(p-1)/2} = 1$$ を使えば分かります。以下、$\sqrt{a} \in \mathbb{Z}/p\mathbb{Z}$ とします。

アルゴリズム

$(\mathbb{Z}/p\mathbb{Z})^\times$ のうち半分の $(p-1)/2$ 個の整数を根として持つ多項式 $f(x):=x^{(p-1)/2}-1$ を用います。ちょうど半分の元を根として持つというのが後々の確率解析に効いてきます。

この多項式の根は $x^2=a \bmod p$ なる $x$ が存在する $a$ （平方剰余）で尽くされます。示しておきます。$\mathbb{Z}/p\mathbb{Z}$ は体なので、根は高々 $(p-1)/2$ 個しか存在しません。$\phi(x)=x^2$ は $\ker(\phi)=\{1,-1\}$ なので、第一同型定理より平方剰余は $(p-1)/2$ 個存在します。従って、平方剰余で $x^{(p-1)/2}-1$ の根が尽くされます。

ランダムな一次式 $h$ により $f(h(x))$ として根を移動させます。すると、$1/2$ 以上の確率（後述）で$$\gcd(f(h), g)$$により $g(x):=x^2-a$ の因数が取り出せます。$$\begin{align} &f(h) \bmod g(x) \\ =& h^{(p-1)/2} – 1 \bmod (x^2-a)\end{align}$$ は繰り返し二乗法により $O(\log p)$ で求まります。従って $k$ 回繰り返せば $1-1/2^k$ 以上の確率で $\sqrt{a} \bmod p$ が見つかります。

確率解析

$\gcd(f(h),g(x)) \neq 1$ かつ $\gcd(f(h),g(x)) \neq g(x)$ となる確率、つまり $g(x)$ の非自明な因数が得られる確率を解析します。

$-\sqrt{a} \neq \sqrt{a}$ つまり $p \neq 2$ と仮定します。中国剰余定理より $g(x)=(x-\sqrt{a})(x+\sqrt{a})$ で取った mod は $\bmod (x-\sqrt{a})$ と $\bmod (x+\sqrt{a})$ の直積と同型です。従って任意の $c_1,c_2 \in \mathbb{Z}/p\mathbb{Z}$ に対して、$$c_1 = h(x) \bmod (x-\sqrt{a}),$$$$c_2=h(x) \bmod (x+\sqrt{a})$$ となる高々一次の多項式 $h(x)$ が一意に存在します。$(\mathbb{Z}/p\mathbb{Z})^\times$ のうち平方剰余/非剰余は半分ずつ存在します。$x$ が平方剰余であることと $f(x)=0$ は同値なので、確率 $\frac{2\frac{p-1}{2}\frac{p+1}{2}}{p^2-p}= \frac{p+1}{2p} > 1/2$ で $g(x)$ の非自明な因数が得られます（分母の $p$ は $h$ が定数の場合を除いた）。

他にも、群構造を使う方法やヤコビ和を使った証明があります[3, 4]。

おまけ

ランダムな整数 $s$ により $g(x-s)$ として根を移動してもアルゴリズムはなんら変わりません（D. H. Lehmer）。 mod sqrt を求める実際の実装においては、こちらの方が簡潔になりますね。

参考文献

Cantor, David G., and Hans Zassenhaus. “A new algorithm for factoring polynomials over finite fields.” Mathematics of Computation (1981): 587-592.
Karp, Richard M. “An introduction to randomized algorithms.” Discrete Applied Mathematics 34.1-3 (1991): 165-201.
Lehmerのアルゴリズムの解析：かならいさんのツイート
Lehmerのアルゴリズムの解析：かならいさんのツイート２