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

Question

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

import numpy as np

# Solving following system of linear equation
# 1a + 1b = 35
# 2a + 4b = 94

a = np.array([[1, 1],[2,4]])
b = np.array([35, 94])

print(np.linalg.solve(a,b))

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

以下形式的方程:

m = 2 ** 31 - 1

(207560540 ∗ a + b) modulo m = 956631177
(956631177 ∗ a + b) modulo m = 2037688522

谢谢。

Answer 1

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

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

由于 m 是质数，因此首先定义反模 m(来自 here ):

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

然后，系统构成:

A1=207560540
C1=956631177
#(A1 ∗ a + b) modulo m = C1  : equation (1)

A2=956631177 
C2=2037688522
#(A2 ∗ a + b) modulo m = C2   : equation (2)

你有:

A = A2-A1  #(2)-(1)
C = C2-C1
#A*a = C  % m
X=inv(A)  
a=(C*X)%m

并且:

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

检查:

print(a,b) 
print((A1*a+b)%m,C1)
print((A2*a+b)%m,C2)

16807 78125  # a and b
956631177 956631177
2037688522 2037688522