CODEWITHSUNDEEP
pythonalgorithmmatrix-inversemodulo
余星佑
余星佑

Reputation: 71

Extend Euclid Algorithm with matrix inverse mod N

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:)

matrix inverse mod N

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?

Upvotes: 2

Views: 226

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

−11 is congruent to 25 mod 36, so in Python you can just take x % N.

Upvotes: 1

Related Questions