使用 Numpy 求解涉及模运算的线性方程

Question

我知道numpy可以用来求解线性方程，如下所示：

\n\n

import numpy as np\n\n# Solving following system of linear equation\n# 1a + 1b = 35\n# 2a + 4b = 94\n\na = np.array([[1, 1],[2,4]])\nb = np.array([35, 94])\n\nprint(np.linalg.solve(a,b))\n

\n\n

现在，假设我有涉及模运算的线性方程。numpy 也能解这样的方程吗？

\n\n

以下形式的方程：

\n\n

m = 2 ** 31 - 1\n\n(207560540 \xe2\x88\x97 a + b) modulo m = 956631177\n(956631177 \xe2\x88\x97 a + b) modulo m = 2037688522\n

\n\n

谢谢。

\n

Answer 1

这是模算术，但不幸的是 numpy 不支持这一点。

\n\n

但你可以在 python 中“手动”解决它。

\n\n

由于m是素数，首先定义逆模m （来自此处）：

\n\n

def inv(x): return pow(x,m-2,m) # inverse mod m, because x**(m-1) %m = 1 (Fermat).\n

\n\n

然后，系统构成：

\n\n

A1=207560540\nC1=956631177\n#(A1 \xe2\x88\x97 a + b) modulo m = C1  : equation (1)\n\nA2=956631177 \nC2=2037688522\n#(A2 \xe2\x88\x97 a + b) modulo m = C2   : equation (2)\n

\n\n

你有 ：

\n\n

A = A2-A1  #(2)-(1)\nC = C2-C1\n#A*a = C  % m\nX=inv(A)  \na=(C*X)%m\n

\n\n

和 ：

\n\n

D = A2*C1-A1*C2  # A2*(1) - A1*(2) \n#A*b = D %m\nb=(D*X)%m\n

\n\n

清理：

\n\n

print(a,b) \nprint((A1*a+b)%m,C1)\nprint((A2*a+b)%m,C2)\n\n16807 78125  # a and b\n956631177 956631177\n2037688522 2037688522\n

\n