python - 带模的线性方程

Question

这就是我真正想要做的

例子:

>>> x = matrix([[5,1],[2,4]])
>>> y = matrix([[1,5],[3,3]])
>>> print x
[[5 1]
 [2 4]]
>>> print y
[[1 5]
 [3 3]]
>>> print x*y % 7
[[1 0]
 [0 1]]

现在，假设我不知道 y。

我可以使用线性方程来计算它，如下所示:

5a + c = 1 mod7
5b + d = 0 mod7
2a + 4c = 0 mod7
2b + 4d = 1 mod7

没有 mod7，我可以这样做:

a = np.array([[5,0,1,0],[0,5,0,1],[2,0,4,0],[0,2,0,4]])
b = np.array([[1,0,1,0]])
x = np.linalg.solve(a,b)

但是如何使用 mod7 来实现呢？

Answer 1

x = y mod7

等于

x = 7k + y

所以，你原来的线性系统

5a      +  c      = 1 mod7
   + 5b      +  d = 0 mod7
2a      + 4c      = 1 mod7
2b           + 4d = 0 mod7

等于

5a      +  c      - 7e = 1
   + 5b      +  d - 7f = 0
2a      + 4c      - 7g = 1
2b           + 4d - 7h = 0

如您所见，您有四个方程式对应八个未知数。所以你不会有唯一的解决方案。