分母が m と互いに素でない場合、「乗法逆剰余」を計算するにはどうすればよいですか?

Question

計算する必要があります (a/b) mod m どこ a そして b 非常に大きな数です。

私がやろうとしているのは計算することです (a mod m) * (x mod m), 、 どこ x それは モジュラーインバース の b.

使ってみた 拡張ユークリッドアルゴリズム, しかし、b と m が互いに素でない場合はどうすればよいでしょうか?具体的には 言及された b と m は互いに素である必要があるということです。

コードを使ってみた ここ, 、そして例えば次のようなことに気づきました。3 * x mod 12 のどのような値でもそれはまったく不可能です x, 、 それは存在しない！

どうすればいいですか？ アルゴリズムを何らかの方法で変更できないでしょうか?

Answer 1

はい、あなたは困っています。xには解がありません b*x = 1 mod m b と m に公約数がある場合。同様に、元の問題では a/b = y mod m, 、あなたはそのようなyを探しています a=by mod m. 。a が次で割り切れる場合 gcd(b,m), 、その後、その係数で除算して y を解くことができます。そうでない場合、方程式を解くことができる y は存在しません (つまり、 a/b mod m 定義されていません）。

Answer 2

b と m が互いに素でなければならない理由は、中国の剰余定理のためです。基本的に問題は次のとおりです。

3 * x mod 12

次のような複合的な問題として考えることができます。

3*x mod 3 そして 3*x mod 4 = 2^2

ここで、b が 12 と互いに素でない場合、これはゼロで除算しようとしているようなものです。したがって、答えは存在しません！

これは抽象代数における場の理論によるものです。フィールドは基本的に、加算、減算、乗算、除算が明確に定義されたセットです。有限体は常に GF(p^n) の形式になります。ここで、p は素数、n は正の整数であり、演算は p^n を法とする加算と乗算です。さて、12 は素数累乗ではないので、 指輪 フィールドではありません。したがって、この問題は、m と互いに素でない b については解くことができません。

Answer 3

これをチェックして： http://www.math.harvard.edu/~sarah/magic/topics/division役立つかもしれません。モジュール分割の方法を説明します。