我需要计算(a/b) mod m在哪里a并且b是非常大的数字。
我要做的是计算的模逆在(a mod m) * (x mod m)哪里。xb
我尝试使用扩展欧几里得算法，但是当 b 和 m 不是互质数时该怎么办？特别提到b和m需要互质。
我尝试使用此处的代码，并意识到例如：
3 * x mod 12对于 的任何值都不可能x，它不存在！
我该怎么办？可以以某种方式修改算法吗？
问问题
12562 次
3 回答
7
是的，你有麻烦了。b*x = 1 mod m如果 b 和 m 有公约数，则x 无解。同样，在您的原始问题a/b = y mod m中，您正在寻找 y 使得a=by mod m。如果 a 可以被 整除gcd(b,m)，那么您可以除以该因子并求解 y。如果不是，则没有 y 可以解方程（即a/b mod m未定义）。
于 2009-10-05T19:05:50.943 回答
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，这个问题都无法解决。
于 2009-10-05T18:59:26.790 回答
1
检查这个： http: //www.math.harvard.edu/~sarah/magic/topics/division 它可能会有所帮助。它解释了模块化划分的方法。
于 2009-10-05T18:57:49.760 回答