我在加密应用程序中面临以下问题:我给出了一组线性同余
a[1]*x[1]+a[2]*x[2]+a[3]*x[3] == d[1] (mod p)
b[1]*x[1]+b[2]*x[2]+b[3]*x[3] == d[2] (mod p)
c[1]*x[1]+c[2]*x[2]+c[3]*x[3] == d[3] (mod p)
这里，x 未知，a、b、c、d 已知
系统很可能是不确定的，所以我有很大的解决方案空间。我需要一种算法，使用伪随机数生成器找到该问题的均匀分布解决方案(这意味着在解决方案空间中均匀分布)(或失败)。
据我所知，我从线性代数类(class)中了解到的大多数线性方程系统标准算法并不直接适用于同余......
我当前的“安全”算法的工作原理如下:查找仅出现在一个方程中的所有变量，并分配一个随机值。现在，如果每一行中只有一个变量未分配，则根据同余分配值。否则失败。
谁能告诉我如何解决这个问题？
最佳答案
您可以使用高斯消去法和类似的算法，就像您在线性代数类(class)中学到的那样，但所有算术都是以 mod p 执行的(p 是素数)。一个重要的区别在于“除法”的定义:要计算 a/b，请改为计算 a * (1/b)(换句话说，“a 乘以 b 的逆”)。考虑对通常使用的数学运算进行以下更改
- 加法:a+b 变为 a+b mod p
- 减法:a-b 变为 a-b mod p
- 乘法:a*b 变为 a*b mod p
- 除法:a/b 变为:如果 p 除 b，则“错误:除以零”，否则 a * (1/b) mod p
要计算 b mod p 的倒数，您可以使用扩展欧几里得算法或计算 b**(p-2) mod p。
与其尝试自己解决这个问题，不如寻找现有的库或包。我认为也许 Sage 可以做到这一点，当然 Mathematica、Maple 和类似的商业数学工具也可以。
关于math - 寻找线性同余系统等分布解的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8503047/