La façon la plus simple d'effectuer une inversion de matrice modulaire avec Python?

un truc hackish qui fonctionne quand les erreurs d'arrondi ne sont pas un problème:

• trouver l'inverse régulier (peut avoir des entrées non-entières), et le déterminant( un entier), tous les deux implémentés dans numpy
• multiplier l'inverse par le déterminant, et Rond À entier (hacky)
• maintenant, multipliez tout par l'inverse multiplicatif du déterminant (modulo votre module, code ci-dessous)
• ne entrywise mod par votre module

Un moins de manière hackish est de mettre en œuvre l'élimination gaussienne. Voici mon code utilisant L'élimination gaussienne, que j'ai écrit pour mes propres fins (les erreurs d'arrondissement étaient un problème pour moi). q est le module, qui n'est pas nécessairement premier.

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

EDIT: comme le font remarquer les commentateurs, il y a des cas où cet algorithme échoue. C'est un peu banal à réparer, et je n'ai pas le temps de nos jours. À l'époque, il fonctionnait pour des matrices aléatoires dans mon cas (les modules étaient des produits de grands nombres premiers). Fondamentalement, la première entrée non nulle pourrait ne pas être relativement premier au module. Le cas principal est facile puisque vous pouvez rechercher une ligne différente et échanger. Dans le cas de non-prime, je pense que ça pourrait être ça les entrées de tête ne sont pas relativement premier donc vous devez les combiner

Ok...pour ceux que ça intéresse, j'ai résolu mon problème. Ça m'a pris du temps, mais je pense que ça marche. C'est probablement pas le plus élégant, et devrait inclure plus d'erreur de manipulation, mais il fonctionne:

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

il peut être calculé en utilisant Sage (www.sagemath.org) comme

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

bien que Sage est énorme à installer et vous devez utiliser la version de python qui vient avec elle qui est une douleur.

malheureusement numpy n'a pas d'implémentations arithmétiques modulaires. Vous pouvez toujours coder l'algorithme proposé en utilisant la réduction de ligne ou les déterminants comme démontré ici. Une inversion modulaire semble être très utile pour la cryptographie.

Ce petit morceau de code semble le faire: lien

Notez le commentaire ci-dessous pour une petite amélioration. Il semble faire l'algèbre linéaire correcte aussi loin que je puisse voir. Je n'ai jamais trouvé d'option dans les paquets réguliers donc probablement prendre un extrait de code sur le web (il y en a beaucoup plus disponible) est l'approche la plus facile.

'sympy' l'ensemble de la Matrice de fonction de classe 'sqMatrix.inv_mod (mod)' calcule une matrice de modulo inverse pour un module petit et arbitrairement grand. En combinant sympy avec numpy, il devient facile de calculer modulo inverse de tableaux numpy 2-D (voir l'extrait de code ci-dessous):

enter code here

import numpy
from sympy import Matrix

    def matInvMod (vmnp, mod):
    nr = vmnp.shape[0]
    nc = vmnp.shape[1]
    if (nr!= nc):
        print "Error: Non square matrix! exiting"
        exit()
    vmsym = Matrix(vmnp)
    vmsymInv = vmsym.inv_mod(mod)
    vmnpInv = numpy.array(vmsymInv)
    print "vmnpInv: ", vmnpInv, "\n"
    k = nr
   vmtest = [[1 for i in range(k)] for j in range(k)]  # just a 2-d list
   vmtestInv = vmsym*vmsymInv
   for i in range(k):
      for j in range(k):
         #print i, j, vmtrx2[i,j] % mod
         vmtest[i][j] = vmtestInv[i,j] % mod
   print "test vmk*vkinv % mod \n:", vmtest
   return vmnpInv

if __name__ == '__main__':
    #p = 271
    p = 

115792089210356248762697446949407573530086143415290314195533631308867097853951 vm = numpy.tableau([[1,1,1,1], [1, 2, 4, 8], [1, 4, 16, 64], [1, 5, 25, 125]])

# vminv = modMatInv (vm, p) vminv = matInvMod(vm, p) imprimer vminv vmtestnp = vm.dot (vminv)%P # test MTRX inversion imprimer vmtestnp

comment faire la matrice de modularité. Calculez la matrice modulaire. Divisez le graphique principal en grappes en utilisant le vecteur d'eigen pour la matrice modulaire. Faites ceci pour chaque cluster créé, de façon itérative( chaque cluster sera alors divisé en deux clusters et ainsi de suite...). Après chaque étape, le nombre de grappes sera deux fois plus élevé. Le critère de regroupement dans cette question Est la modularité. À cette fin, à chaque étape calculer le critère de modularité et arrêter l'algorithme où il est dégressif.

en python