今回はアルゴリズムについての話題で、Abundance of Witnesses (AoW) についてのメモです。
判定問題を決定論的に解くよりも効率的に、かなり正確に解を出すことができます。
弊社も AtCoder コンテストの冠スポンサーになったらしいですから時にはアルゴリズムについて学んでみようと思います。
tl:dr
判定問題において、関連する問題、部分問題などを乱択で解くようにしてみると元の問題が物凄く効率的に解ける場合があります。
乱択を用いて素数判定を行う Miller-Rabin 素数判定法は RSA 暗号にも用いられています。
Abundance of Witnesses (AoW)
Witness (証人)
入力 $x$ を持つある判定問題 $P$ に対する $witness$ とは、入力 $x$ とは異なる付加的な情報であって、判定問題の解を保証してくれるものです。
例えば、次のようなケースを考えてみましょう。
2022 は素数か判定せよ。
このとき、$2$ は $witness$ です。なぜなら、$2$ は $2022$ と異なる数でありながら $2022$ の素因数であるため、「$2022$ が素数でないこと」の証人となるからです。
次のケースではどうでしょうか。
2023 は素数か判定せよ。
$2, 3, 5$ で試し割りをしてみると、いずれでも割り切れないようです。これらの数字は割り切れれば「$2023$ が素数でないこと」の証人となり得ますが、割り切れないなら逆に「$2023$ が素数であること」の証人となるでしょうか。なり得ませんね。
このように、$witness$ は多くの場合真偽値の片側しか保証ができません。
Abundance of Witnesses (潤沢な証人達?)
$witness$ が多く存在するような問題では、$witness$ の候補となるような元をいくつか選んで試行をすれば高い確率で正解が得られる、という技法です。$witness$ 単体では真偽値の片側しか保証ができませんでしたが、「充分多くの $witness$ 候補に対して試行をしたのに $witness$ が得られなかった」なら「$witness$ が保証しない方の解を採択できる」という理屈になります。
ここからは AoW を用いた問題解決の例を紹介します。
Miller-Rabin 素数判定法
RSA 暗号に必要な素数を生成するのに使われるアルゴリズムです。
1以上の整数 $N$ が与えられる。$N$ が素数か判定せよ。
試し割り法でナイーブに判定すると $O(\sqrt{N})$ 程度の計算量が必要になります。これは、$2$ から $\sqrt{N}$ までの整数で $N$ を割り切るものがあるか調べる方法です。
試し割り法がなぜ $O(\sqrt{N})$ ？
例えば $100$ が素数かどうか確かめたいなら、$2$ から $10$ までの数で割り切れるかどうか確かめれば十分です。
$20$ など $10$ より大きい数で割れるか確かめる必要はありません。何故なら $100$ を $5$ で割った時の商が既に $20$ だからです。
$1$ 以上の整数 $N$ は $1$ 以上の別の整数 $p, q$ で $N=pq$ と表せます。$p \ge \sqrt{N}$ の場合、必ず $q \le \sqrt{N}$ ですから先に $q$ で割れるか見られているという理屈です。
AoW を使うと全く異なるアプローチで驚異的な高速化ができます。
まず、$witness$ の候補となる整数 $w$ を用意します。$N$ が素数なら下式が成り立ちます。（Fermat の小定理)
$$w^{N-1}\equiv 1 \mod{N}$$
逆にこれが成り立たないようであれば $w$ は「$N$ が素数でないこと」の $witness$ です。
ところで、この式は $N$ が素数でない場合にもしばしば成り立ってしまいます。($N$ と $w$ が互いに素な時など)
これを解決するため、今度は剰余環上の平方根を考えます。
$N$ が素数なら $x^2\equiv 1 \mod N$ なる $x$ は $1, N-1$ 以外にあり得ません。逆に $N$ が合成数なら $x$ はこれ以外の数も取ります。これがうまく使えそうです。
なぜ $N$ が素数のとき $x^2\equiv 1$ なる $x$ は $1, N-1$ しかないのか？
$x^2\equiv 1 \mod N$ を式変形して $(x-1)(x+1)\equiv 0 \mod N$ を得ます。$x\equiv 1, N-1 \mod N$ は自明な解です。
これ以外が解となる場合、$x-1\not\equiv 0$, $x+1\not\equiv 0$, $(x-1)(x+1)\equiv 0 \mod N$ を満たす必要がありますが、
$N$ が素数なので $1, N$ 以外の約数を持たないことから
$x-1\equiv 1$, $x+1\equiv N \mod N$ となってしまい、$x+1\not\equiv 0 \mod N$ に矛盾してしまいます。
逆に $N$ が合成数の時は例えば $N=8$ のとき $x\equiv 3$, $x^2\equiv 1 \mod N$ になってしまいます。
$w^{k2^d}$ の平方根を取っていって、$w^{k2^j}\equiv 1 \mod N$ かつ $w^{k2^{j-1}}\not\equiv 1, N-1 \mod N$ である $j$ が見つかれば、$w$ は「$N$ が素数でないこと」の $witness$ であると言えます。
平方根？
$w^{k2^j}$ の平方根を計算したければ $w^{k2^{j-1}}$ を計算すればよいです。$w^k$ から $w^{k2^d}$ までの計算は全体で $\mathcal{O}(\log{N})$ ほどの計算量となります。
後はこのような $w$ がどのくらいの確率で見つかるか、ということですがランダムに選べば $3/4$ 程度の確率で合成数をそうであると判断してくれるような $w$ が見つかることが知られています。複数の $w$ を用いて判定を行えば指数関数的に判定の正確さを上昇させることができます。
計算量は $\mathcal{O}(\log N)$ ほどです
Freivalds の行列積判定
$N\times N $ の正方行列 $\rm{A}, \rm{B}, \rm{C}$ が与えられる。$\rm{A}\times \rm{B} = \rm{C}$ が成り立つかどうかを判定せよ。
愚直に計算すれば行列積の計算がボトルネックとなり全体として $\mathcal{O}(N^3)$ の計算量がかかります。
AoW で高速化を試みます。
まず、$N$ 次元のランダムな行ベクトル $w$ を用意して次のように式変形をします。
$$\rm{A}\times \rm{B}\times \it{w} = \rm{C}\times \it{w}$$
この等式が成り立つことは元の等式が成り立つことと等価ではありませんが、この等式が成り立たないことは元の等式が成り立たないことの必要十分条件です。
ここで、行列積は結合法則が成り立つので次のように括弧でくくって計算できます。
$$\rm{A}\times (\rm{B}\times \it{w}\rm) = \rm{C}\times \it{w}$$
$N\times N $ の正方行列と $N$ 次元ベクトルとの積の計算は $\mathcal{O}(N^2)$ で完了し、計算の結果得られるは $N$ 次元ベクトルとなります。従って左辺も右辺も積の計算が $\mathcal{O}(N^2)$ で遂行できるので全体としての計算量は $\mathcal{O}(N^2)$ になります。
衝突確率
$\rm A\times B\neq C$ でかつ $\rm{A}\times \rm{B}\times \it{w} = \rm{C}\times \it{w}$ になる確率はどのくらいか見積もります。$\rm D=C-A\times B$ として、ある $i,j$ について $D_{i,j}\neq0$ でかつ $\rm{D}\it{w}=0$ となるためには、
$$D_{i,j}w_j=-\sum_{k\neq j}D_{i,k}w_k$$
を満たす必要があります。
この式が $w_j$ の値をただ一通りに束縛することから、$w_j$ の値を $M$ 種類のうちから選ぶとしたら衝突確率は高々 $1/M$ となります。
複数の $w$ を用いて判定を行えば指数関数的に衝突確率を減少させることができます。
おわりに
がんばって書いたところで気付いたんですが、競技プログラミングでこの手の乱択アルゴリズムが直接問われるような出題はあまりない気がしてきました。
涙が止まりません。