Использование 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 (из здесь ):

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