math - 反转mod的功能？

Question

我正在尝试解决这个等式：

(b(ax+b ) - c) % n = e 

除了x 我尝试了以下方法之外，一切都给出了：

(A + x) % B = C
(B + C - A) % B = x

在哪里A，(-c)然后手动解决给x定我的其他潜艇，但我没有得到正确的输出。我可能需要使用eea吗？任何帮助，将不胜感激！我知道有人问过这个问题，我尝试了他们的解决方案，但对我不起作用。

标签： mathmod

Answer 1

(b*(a*x+b) - c) % n = e

可以改写为：

(b*a*x) % n = (e - b*b + c) % n
x = ((e - b*b + c) * modular_inverse(b*a, n)) % n

其中 , 的模逆是这样的数字。有关计算模逆的代码，请参见此问题。umodular_inverse(u, n)vu*v % n == 1

一些警告：

• 当简化模方程时，你永远不能简单地除法，你需要乘以模逆。
• 没有直接的公式来计算模逆，但是有一个简单、快速的算法来计算它，类似于计算gcd。
• 模逆并不总是存在。
• 根据编程语言，当一个或两个参数为负时，模的结果也可能为负。
• 由于每个解决方案都适用于每个xmodulo ，因此只有n少量的数字需要测试，所以在许多情况下，一个简单的循环就足够了。n0n-1