5

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.

Neon Flash
  • 3,113
  • 12
  • 58
  • 96
  • 2
    With `modulo operation`, the equation is no longer `linear`. – swatchai Dec 22 '18 at 01:41
  • @swatchai These equations are based on LCG (Linear Congruence Generator) as described here: https://en.wikipedia.org/wiki/Linear_congruential_generator. So, you mean LCG does not use linear equations? Maybe they are a variant of linear equations? – Neon Flash Dec 22 '18 at 01:57

2 Answers2

5

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
B. M.
  • 18,243
  • 2
  • 35
  • 54
  • could you explain how to extend this to n of these equations, i.e. x[i] = (x[i-1] ∗ a + b) modulo , i=1,..,n ? – jbbj94 Jan 16 '23 at 20:47
1

You could try to rewrite this into a normal linear system. Something like this:

(207560540 ∗ a + b) + c*m + d*0 = 956631177
(956631177 ∗ a + b) + c*0 + d m = 2037688522

If you now solve this linear system you should get your answer.

win8789
  • 65
  • 8
  • How do you want to solve this system of linear equations and guarantee that c and d are integer values? – HermannSW Jul 02 '22 at 12:59