逆元を使うことで、与えられた数が特定の数の倍数かどうかを、1回の判定ごとに分岐や除算を使わずに判定することができます。
前提条件
以下では、特定のビット幅に収まる、符号なし整数の倍数判定を行います。
- 符号付き整数には応用可能ですが、煩雑となりますので割愛します。
- 無限に大きくなりうる値に対して適用することは不可能です。
- C言語の符号なし整数のような、「オーバーフローすれば黙って下位ビットを取り出す」環境なら実行がやりやすいですが、そうでない場合は下位ビットだけ取り出すようなマスクが必要となります。
つまり、倍数判定は $\mod 2^b$ の世界で行います（$b$はビット数です）。$0$ 以上 $2^b$ 未満である $x$ について、$d$ の倍数かを判定する、というように変数を置きます。また、$d$ は事前に決まっている前提です。
逆元とは
実数の演算で、$x$ に対して $1/x$ を「逆数」と呼びますが、それと同様に、$\mod 2^b$ の世界でも、ある数 $d$ に対して $d\overline{d} \equiv 1\pmod{2^b}$ となるような $\overline{d}$ を考えることができ、これを「逆元」と呼びます。
なお、逆元 $\overline{d}$ は、$d$ と $2^b$ が互いに素となる場合、つまり $d$ が奇数の場合のみ存在します。
奇数の場合
基本的なパターンである、$d$ が奇数の場合を先に考えます。この場合、逆元 $\overline{d}$ が存在して、もちろん奇数（$2^b$ とは互いに素）です。
$d$ の倍数である $x = kd$ を持ってきた場合、$ x\overline{d} = kd\overline{d} \equiv k\pmod{2^b}$ となり、$\mod 2^b$ の世界での $ x\overline{d}$ の演算結果は、$x$ を $d$ で割った商に一致します。
ここで、$\overline{d}$ と $2^b$ は互いに素なので、$0,\ \overline{d},\ 2\overline{d},\ \cdots\ (2^b-1)\overline{d}$ という $2^b$ 個の値は、$\mod 2^b$ の世界ですべて違う値（可能な $2^b$ 通りの値の全パターン）を取ります。
そのため、$d$ の倍数である $x$ について、$x\overline{d}$ は前述のように $0$ 以上 $(2^b-1)/d$ 以下の値を取るのに対して、$x$ が $d$ の倍数でない場合には残りの値である $(2^b-1)/d$ より大きなところとなります。これを利用して倍数の判別が可能です。
偶数の場合
$d$ が偶数の場合、2の冪を分けて $d = 2^sk$ （$k$ は奇数）としておきます。$k$ の$\mod 2^b$ の世界での逆元 $\overline{k}$ を用意して、$x\overline{k}$ を計算すれば、満たすべき条件は以下の2つです。
- 下位 $s$ ビットは全て0
- 全体が $(2^b-1)/k$ 以下
これを一気に評価するため、$x\overline{k}$ を $s$ ビットだけ右ローテートして、前者の条件を上位ビットで判定できるようにしておけば、「全体が $(2^b-1)/d$ 以下」という条件1つで片付くようになります。
逆元の算出方法
逆元があれば判定ができるようになったのはいいのですが、肝心の逆元はどうやって得ればいいのでしょうか。手早く済むのがニュートン法です。
初期値の $x_0$ を用意して、あとは $x_{n + 1} \equiv x_n(2 - dx_n)\pmod{2^b}$ を収束するまで繰り返すだけです。こちらにあるように、1ステップで正しい桁が2倍になっていくので、すぐ終わります。
初期値としては1でも構わないですが、奇数である任意の $x$ について $x^2 \equiv 1 \pmod{2^3}$ が成り立つので、$d$ をそのまま使うだけでも下位3ビットが正しい状態からのスタートとなり、1から始めるより計算を1ステップ以上減らせます。
参考文献
- ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか オンデマンド版（ヘンリー・S. ウォーレン ジュニア著、エスアイビー・アクセス、2014年。ISBN 978-4-434-20159-2）§10-16 定数による除算後に剰余が0か調べる