(a/b) mod mどこでaとbが非常に大きいかを計算する必要があります。
私がやろうとしているのは、 を計算する(a mod m) * (x mod m)ことです。xb
拡張ユークリッド アルゴリズムを使用してみましたが、b と m が互いに素でない場合はどうすればよいですか? b と m が互いに素である必要があることが特に言及されています。
コードhereを使用してみましたが、たとえば
3 * x mod 12、 の値に対して はまったく不可能でありx、存在しないことに気付きました!
私は何をすべきか？アルゴリズムを何らかの方法で変更できますか?
ええ、あなたは困っています。b*x = 1 mod mb と m が公約数を持つ場合、x には解がありません。同様に、元の問題a/b = y mod mでは、 のような y を探していa=by mod mます。a が で割り切れる場合、gcd(b,m)その係数で割って y を解くことができます。そうでない場合、方程式を解くことができる y はありa/b mod mません (つまり、定義されていません)。
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 については解決できません。
これを確認してください: http://www.math.harvard.edu/~sarah/magic/topics/division 役立つかもしれません。モジュラー分割の方法について説明します。