如何计算“模乘逆”当分母不与 m 互质时？
我需要计算 (a/b) mod m，其中 a 和 b< /code>是非常大的数字。
我想做的是计算 (a mod m) * (x mod m)，其中 x > 是 b 的 模逆 。
我尝试使用 扩展欧几里得算法，但是当 b 和 m 不互质时该怎么办？ 特别提到 b 和 m 需要互质。
我尝试使用代码此处，并意识到例如： 3 * x mod 12对于x的任何值都是不可能的，它不存在！
我应该做什么？可以以某种方式修改算法吗？
I need to calculate (a/b) mod m where a and b are very large numbers.
What I am trying to do is to calculate (a mod m) * (x mod m), where x is the modular inverse of b.
I tried using Extended Euclidean algorithm, but what to do when b and m are not co-prime?
It is specifically mentioned that b and m need to be co-prime.
I tried using the code here, and realized that for example:3 * x mod 12 is not at all possible for any value of x, it does not exist!
What should I do? Can the algorithm be modified somehow?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的，你有麻烦了。如果 b 和 m 有公约数，则 x 在
b*x = 1 mod m中无解。同样，在原始问题a/b = y mod m中，您正在寻找 y 使得a=by mod m。如果 a 可以被 gcd(b,m) 整除，那么您可以除以该因子并求解 y。如果不是，则没有 y 可以解方程（即未定义 a/b mod m）。Yep, you are in trouble. x has no solution in
b*x = 1 mod mif b and m have a common divisor. Similarly, in your original problema/b = y mod m, you are looking for y such thata=by mod m. If a is divisible bygcd(b,m), then you can divide out by that factor and solve for y. If not, then there is no y that can solve the equation (i.e.a/b mod mis not defined).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，这个问题都无法解决。
The reason that b and m have to be coprime is because of the Chinese Remainder Theorem. Basically the problem:
3 * x mod 12Can be thought of as a compound problem involving
3*x mod 3and3*x mod 4 = 2^2Now if b is not coprime to 12, this is like trying to divide by zero. Thus the answer doesn't exist!
This is due to field theory in abstract algebra. A field is basically a set which has addition, subtraction, multiplication, and division well-defined. A finite field is always of the form GF(p^n), where p is prime and n is a positive integer, and the operations are addition and multiplication modulo p^n. Now, 12 is not a prime power, so your ring is not a field. Thus this problem can't be solved for any b which is not coprime to m.
检查这个：http://www.math.harvard.edu/~sarah /magic/topics/division
这可能有帮助。
它解释了模块划分的方法。
Check this: http://www.math.harvard.edu/~sarah/magic/topics/division
It might help.
It explains methods of modular division.