22

Python で [[1,2],[3,4]] mod 7 のような行列のモジュラー逆を取りたいと思います。私はnumpy（行列の反転を行いますが、剰余行列の反転は行いません）を見て、いくつかの数論パッケージをオンラインで見ましたが、この比較的一般的な手順を実行しているようには見えません（少なくとも、私には比較的一般的です）。

ちなみに、上の行列の逆行列は [[5,1],[5,3]] (mod 7) です。私はPythonにそれをやってもらいたいと思っています。

4

5 に答える 5

12

丸め誤差が問題にならない場合に機能するハックなトリック:

  • 通常の逆数 (整数以外のエントリがある場合があります) と行列式 (整数) を見つけます。どちらも numpy で実装されています
  • 逆数に行列式を掛け、整数に丸めます (ハッキー)
  • すべてを行列式の乗法逆数で乗算します（モジュロモジュラス、以下のコード）
  • あなたのモジュラスでエントリごとの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

EDIT：コメント者が指摘しているように、このアルゴリズムが失敗する場合があります。修正するのは少し面倒で、今日は時間がありません。当時、私の場合はランダム行列で機能していました（係数は大きな素数の積でした）。基本的に、ゼロ以外の最初のエントリは、モジュラスに対して相対的に素ではない可能性があります。別の行を検索してスワップできるため、主要なケースは簡単です。非素数の場合、すべての主要なエントリが比較的素数ではない可能性があるため、それらを組み合わせる必要があると思います

于 2011-07-14T22:38:55.553 に答える
12

わかりました...気にする人のために、私は自分の問題を解決しました。少し時間がかかりましたが、これでうまくいくと思います。これはおそらく最も洗練されたものではなく、エラー処理を追加する必要がありますが、機能します。

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
于 2010-11-27T18:10:28.713 に答える
5

これは、Sage ( www.sagemath.org )を使用して次のように計算できます。

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

Sage はインストールするのが巨大で、それに付属しているバージョンの Python を使用する必要がありますが、これは面倒です。

于 2014-10-21T23:27:54.930 に答える
2

残念ながら、numpy にはモジュラ演算の実装がありません。ここで示されているように、行削減または行列式を使用して、提案されたアルゴリズムをいつでもコード化できます。モジュラー逆数は、暗号化に非常に役立つようです。

于 2010-11-26T19:09:33.580 に答える