我在密码学应用中面临以下问题:我给定了一组线性同余
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是已知的
系统很可能是待定的，所以我有一个大的解空间。我需要一种算法，使用伪随机数生成器(或失败)找到该问题的等分布解(即在解空间中等分布)。
我从线性代数课程中学到的大多数线性方程组的标准算法在我看来都不能直接应用于同余…
我目前的"安全"算法是这样工作的:找到只出现在一个方程中的所有变量，并分配一个随机值。现在，如果在每一行中只有一个变量未赋值，则根据同余值赋值。否则失败。
谁能给我一个提示，如何解决这个问题总的来说?你可以使用高斯消去和类似的算法，就像你在线性代数课程中学到的那样，但所有的算术都是对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模p的逆，你可以使用扩展欧几里得算法，或者计算b**(p-2)模p。
与其尝试自己滚动，不如查找现有的库或包。我想也许Sage可以做到这一点，当然Mathematica和Maple，以及类似的商业数学工具也可以。