为函数反转 mod？

Question

我正在尝试求解这个方程式：

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

除了 x 之外的所有内容 我尝试了 :

的方法

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

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

Answer 1

你用什么语言做的，变量是常量吗？ 这是确定 Java:

中 x 的可能值的快速方法

for (int x = -1000; x < 1000; x++){
    if ((b*((a*x)+b) - c) % n == e){
    System.out.println(x);
    }
}

Answer 2

(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

其中 modular inverse of u, modular_inverse(u, n), is a number v such that u*v % n == 1. See this question 用于计算模逆的代码。

一些注意事项：

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