mod 上での除算 / 逆元
ということで、mod 上で除算をする方法について書きます。
そもそも、mod 上での除算はどうして難しいと言われているのか
シンプルに、普通に割ることが出来ません。
例えば、$ 25 \div 5 = 5ですが、
$ \bmod \ 7では$ 25 \equiv 4 \bmod 7です。
当たり前ながら、$ 4を$ 5で割ることは出来ません。
よって、例えばなんか適当な加減算、乗算をして$ P以上の整数を$ Pで割った余りの値で扱っている時は、ほぼ確実に、正当にその値に対して割り算をすることが出来ません。
除算をする方法
いくつか方法がありますが、一般に簡単と言われているほうからいきましょう。
フェルマーの小定理を用いる
注意：この方法は$ Pが素数である場合のみ可能です。
$ A \div B \equiv C \bmod Pとして$ Cを求めることを考えます。
フェルマーの小定理とは、$ aが$ \bmod \ Pにおいて$ 0でないとしたときに
$ a^{P-2} \equiv 1 \bmod P
が成り立つ、という定理です。
証明については調べるとそこら中に出てくるので割愛します。
左辺を変形します。
$ a \cdot a^{P-2} \equiv 1 \bmod P
これをよく睨むと、$ aと$ a^{P-2}の積が$ 1であるということは、$ 1 \div a \equiv a^{P-2} \bmod Pと言えます。
では、これを$ A \div B \equiv C \bmod Pという式に活用するとどうなるかというと、
まずは$ 1 \div B \equiv B^{P-2} \bmod Pとなります。
ここで、$ A(1 \div B) = A \div Bですので、$ A \div B \equiv A \cdot B^{P-2} \bmod Pとなります。
ということは、$ Aと$ B^{P-2}を掛ければ割り算ができる、ということになります。
なお、この$ B^{P-2}を$ \bmod \ Pにおける$ Bの逆元と呼びます。
$ B^{P-2} \bmod Pを求めることは、繰り返し二乗法を用いれば$ Ο(\log P)で出来ます。
よって、一般的に十分高速な計算時間で除算をできました。
実際に、$ 25 \div 5を$ \bmod \ 7上で行います。
$ 4 \div 5 \equiv 4 \times (5^5 \bmod 7) \equiv 4 \times 3 \equiv 5となって、$ 25 \div 5をそのまま計算したあと$ \bmodを取った場合と同じ結果を得られました。