使用Python执行模块化矩阵反转的最简单方法？

Question

我想在Python中采用像[[1,2],[3,4]] mod 7这样的矩阵的模逆.我看过numpy(它进行矩阵求逆而不是模块矩阵求逆),我在网上看到了一些数论包,但似乎没有什么比较常见的程序(至少对我而言似乎相对常见).

顺便说一下,上述矩阵的逆是[[5,1],[5,3]](mod 7).我希望Python能为我做这件事.

Answer 1

舍入错误时有效的hackish技巧不是问题:

• 找到常规逆(可能有非整数条目)和行列式(整数),都是在numpy中实现的
• 将倒数乘以行列式,并舍入为整数(hacky)
• 现在将所有东西乘以行列式的乘法逆(以模数为模,代码如下)
• 按模数进行入门mod

一种不那么强硬的方式是实际实现高斯消除.这是我的代码使用高斯消除,我为自己的目的写的(舍入错误对我来说是一个问题).q是模数,不一定是素数.

def generalizedEuclidianAlgorithm(a, b):
    if b > a:
        return generalizedEuclidianAlgorithm(b,a);
    elif b == 0:
        return (1, 0);
    else:
        (x, y) = generalizedEuclidianAlgorithm(b, a % b);
        return (y, x - (a / b) * y)

def inversemodp(a, p):
    a = a % p
    if (a == 0):
        print "a is 0 mod p"
        return None
    if a > 1 and p % a == 0:
        return None
    (x,y) = generalizedEuclidianAlgorithm(p, a % p);
    inv = y % p
    assert (inv * a) % p == 1
    return inv

def identitymatrix(n):
    return [[long(x == y) for x in range(0, n)] for y in range(0, n)]

def inversematrix(matrix, q):
    n = len(matrix)
    A = np.matrix([[ matrix[j, i] for i in range(0,n)] for j in range(0, n)], dtype = long)
    Ainv = np.matrix(identitymatrix(n), dtype = long)
    for i in range(0, n):
        factor = inversemodp(A[i,i], q)
        if factor is None:
             raise ValueError("TODO: deal with this case")
        A[i] = A[i] * factor % q
        Ainv[i] = Ainv[i] * factor % q
        for j in range(0, n):
            if (i != j):
                factor = A[j, i]
                A[j] = (A[j] - factor * A[i]) % q
                Ainv[j] = (Ainv[j] - factor * Ainv[i]) % q
    return Ainv

编辑:正如评论者指出的那样,在某些情况下这种算法失败了.修复它有点不重要,现在我没有时间.那时它适用于我的情况下的随机矩阵(模数是大素数的乘积).基本上,第一个非零项可能不是模数的相对素数.主要情况很简单,因为您可以搜索不同的行并进行交换.在非素数情况下,我认为可能所有主要条目都不是相对素数,因此您必须将它们组合在一起

Answer 2

好吧......对于那些关心的人,我解决了自己的问题.我花了一段时间,但我觉得这很有效.它可能不是最优雅的,应该包含一些更多的错误处理,但它的工作原理:

import numpy
import math
from numpy import matrix
from numpy import linalg

def modMatInv(A,p):       # Finds the inverse of matrix A mod p
  n=len(A)
  A=matrix(A)
  adj=numpy.zeros(shape=(n,n))
  for i in range(0,n):
    for j in range(0,n):
      adj[i][j]=((-1)**(i+j)*int(round(linalg.det(minor(A,j,i)))))%p
  return (modInv(int(round(linalg.det(A))),p)*adj)%p

def modInv(a,p):          # Finds the inverse of a mod p, if it exists
  for i in range(1,p):
    if (i*a)%p==1:
      return i
  raise ValueError(str(a)+" has no inverse mod "+str(p))

def minor(A,i,j):    # Return matrix A with the ith row and jth column deleted
  A=numpy.array(A)
  minor=numpy.zeros(shape=(len(A)-1,len(A)-1))
  p=0
  for s in range(0,len(minor)):
    if p==i:
      p=p+1
    q=0
    for t in range(0,len(minor)):
      if q==j:
        q=q+1
      minor[s][t]=A[p][q]
      q=q+1
    p=p+1
  return minor

Answer 3

它可以使用 Sage ( www.sagemath.org ) 计算为

Matrix(IntegerModRing(7), [[1, 2], [3,4]]).inverse()

虽然Sage安装起来很大，而且你必须使用它附带的python版本，这很痛苦。

Answer 4

不幸的是 numpy 没有模块化算术实现。您始终可以使用行缩减或行列式来编写建议的算法，如此处所示。模逆似乎对于密码学非常有用。