は私が計算する必要がaとbは非常に大きな数字です(a/b) mod m。私がやろうとしています何分母がmとコプライムしていない場合の「モジュラ乗法逆行列」の計算方法は？
はbのmodular inverseですx、(a mod m) * (x mod m)を計算することです。
私はExtended Euclidean algorithmを使ってみましたが、bとmがコプライムでない場合はどうしたらいいですか？ 具体的には、mentionedで、bとmはコプライムである必要があります。
私はコードhereを使用してみました、そして例えば気づい： 3 * x mod 12が可能なすべてのxの任意の値のではない、それは存在しません！
どうすればよいですか？アルゴリズムは何とか変更できますか？
あなたは困っています。 bとmに共通の除数がある場合、xはb*x = 1 mod mには解を持ちません。同様に、元の問題a/b = y mod mでは、a=by mod mのようなyを探しています。 aがgcd(b,m)で割り切れる場合、その因子で除算してyを解くことができます。そうでない場合、方程式を解くことができるyがない（すなわち、a/b mod mは定義されていない）。
これを確認してください：http://www.math.harvard.edu/~sarah/magic/topics/division モジュラ除算の方法について説明します。
@aakash今すぐに入手しました – avd
bとmが共起しなければならない理由は、中国の剰余定理のためです。基本的には問題：
3 * x mod 12
は、bは12と互いに素の関係にされていない場合
3*x mod 3と今3*x mod 4 = 2^2
を含む化合物の問題として考えることができますが、これはゼロで除算しようとしているようなものです。したがって、答えは存在しません！
これは抽象代数の場理論によるものです。フィールドは、基本的に加算、減算、乗算、および除算が明確に定義されたセットです。有限体は常にGF（p^n）の形をとり、pは素数でnは正の整数であり、演算はp^nを法とした加算と乗算である。今、12は素数ではないので、のリングはフィールドではありません。したがって、この問題は、mと共起しないbについては解くことができない。
@Keith Randallだから、これを解決するには何ができますか？ – Lazer
私はあなたが何を意味するか分からない。 aがgcd（b、m）で割り切れる場合は、それを解くことができます。それ以外の場合、除算演算は定義されません。あなたはモジュール分割なしにあなたの究極の目標を達成する別の方法を見つけ出す必要があります。 –
私は、「モジュール分割なしの私の究極の目的を達成する」他の方法は何ができるのでしょうか？ – Lazer