I am implementing an extended Eucilid algorithm with matrix mod N
. This is my code implementation:
def eea(a, b): if not isinstance(a, int) or not isinstance(b, int) or not a or not b: result = 'Error(eea): Invalid input num' else: original_a = a original_b = b x, y, u, v = (0, 1, 1, 0) while a != 0: q, r = (b // a, b % a) m, n = (x - u * q, y - v * q) b, a, x, y, u, v = (a, r, u, v, m, n) cnsm = b result = [cnsm, x, y] if original_a < 0 and original_b < 0: result[0] = abs(result[0]) result[1] = -1 * result[1] result[2] = -1 * result[2] if result[0] < 0: result = [abs(result[0]), x, y] if original_a < 0 < original_b or original_b < 0 < original_a: result[2] = -1 * result[2] if result[0] > 0: if original_b < 0 < original_a: result[2] = -1 * result[2] return result
Now, I need to calculate the matrix inverse mod 36
with the following matrix:
[3, 2] [4, 7]
(This is the video link:)
However, my code can only get x = -11, y = -4
, exactly it is a solution of equation 13x = 36y + 1
, but in the video the solution is x = 25, y = 9
, so how do I change my code to meet this situation?
Advertisement
Answer
−11 is congruent to 25 mod 36, so in Python you can just take x % N
.