用矩阵求逆 mod N 扩展 Euclid 算法

Question

我正在用矩阵 mod N 实现 extended Eucilid algorithm。这是我的代码实现：

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

现在，我需要使用以下矩阵计算逆矩阵 mod 36：

[3, 2]
[4, 7]

（这是视频 link:)

matrix inverse mod N

但是我的代码只能得到x = -11, y = -4，正好是方程13x = 36y + 1的解，但是视频中的解是x = 25, y = 9，请问如何修改我的遇到这种情况的代码？

Answer 1

−11 等于 25 mod 36，所以在 Python 中你可以只取 x % N.

用矩阵求逆 mod N 扩展 Euclid 算法

Extend Euclid Algorithm with matrix inverse mod N

python

algorithm

matrix-inverse

mod