I know that numpy can be used to solve linear equations as shown below:
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))
Now, let's say, I have linear equations which involve the modulo operation. Can numpy solve such equations as well?
Equations of the following form:
m = 2 ** 31 - 1
(207560540 ∗ a + b) modulo m = 956631177
(956631177 ∗ a + b) modulo m = 2037688522
Thanks.
To solve a linear congruence ax ≡ b (mod N), you can multiply by the inverse of a if gcd(a,N) = 1; otherwise, more care is needed, and there will either be no solutions or several (exactly gcd(a,N) total) solutions for x mod N.
The Numpy library can be used to perform a variety of mathematical/scientific operations such as matrix cross and dot products, finding sine and cosine values, Fourier transform and shape manipulation, etc.
This is modular arithmetic, but unfortunately numpy doesn't support this.
But you can solve it "manually" in python.
Since m
is prime, first define the inverse modulo m
(from here):
def inv(x): return pow(x,m-2,m) # inverse mod m, because x**(m-1) %m = 1 (Fermat).
Then, with the system posed as :
A1=207560540
C1=956631177
#(A1 ∗ a + b) modulo m = C1 : equation (1)
A2=956631177
C2=2037688522
#(A2 ∗ a + b) modulo m = C2 : equation (2)
You have :
A = A2-A1 #(2)-(1)
C = C2-C1
#A*a = C % m
X=inv(A)
a=(C*X)%m
And :
D = A2*C1-A1*C2 # A2*(1) - A1*(2)
#A*b = D %m
b=(D*X)%m
Check-up:
print(a,b)
print((A1*a+b)%m,C1)
print((A2*a+b)%m,C2)
16807 78125 # a and b
956631177 956631177
2037688522 2037688522
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With