10

私のプロジェクトでは、行列 Y と K を指定して行列 X を解く必要があります。(XY=K) 各行列の要素は、ランダムな 256 ビット素数を法とする整数でなければなりません。この問題を解決するための最初の試みは、SymPy のmod_inv(n)関数を使用しました。これに関する問題は、約 30 のサイズの行列でメモリが不足していることです。次に考えたのは、行列の因数分解を実行することでした。ただし、SymPy には、数を法とする行列を見つけることができるソルバーが含まれていないようです。使用できる回避策や自作のコードはありますか?

4

1 に答える 1

15

sympyのMatrixクラスはモジュラー逆数をサポートします。モジュロ 5 の例を次に示します。

from sympy import Matrix, pprint

A = Matrix([
    [5,6],
    [7,9]
])

#Find inverse of A modulo 26
A_inv = A.inv_mod(5)
pprint(A_inv)

#Prints the inverse of A modulo 5:
#[3  3]
#[    ]
#[1  0]

rref行削減階層形式を見つける方法は、行列内のどのエントリをゼロとして扱う必要があるかを示すキーワードをサポートしていiszerofunctionます。私は確信が持てませんが、意図された用途は数値安定性（小さな数をゼロとして扱う）のためだと思います。モジュール削減に使用しました。

モジュロ 5 の例を次に示します。

from sympy import Matrix, Rational, mod_inverse, pprint

B = Matrix([
        [2,2,3,2,2],
        [2,3,1,1,4],
        [0,0,0,1,0],
        [4,1,2,2,3]
])

#Find row-reduced echolon form of B modulo 5:
B_rref = B.rref(iszerofunc=lambda x: x % 5==0)

pprint(B_rref)

# Returns row-reduced echelon form of B modulo 5, along with pivot columns:
# ([1  0  7/2  0  -1], [0, 1, 3])
#  [                ]
#  [0  1  -2   0  2 ]
#  [                ]
#  [0  0   0   1  0 ]
#  [                ]
#  [0  0  -10  0  5 ]

rref[0]によって返される行列にまだ 5 と分数が含まれていることを除けば、これはある程度正しいことです。mod を取り、分数を剰余逆数として解釈することで、これに対処します。

def mod(x,modulus):
    numer, denom = x.as_numer_denom()
    return numer*mod_inverse(denom,modulus) % modulus

pprint(B_rref[0].applyfunc(lambda x: mod(x,5)))

#returns
#[1  0  1  0  4]
#[             ]
#[0  1  3  0  2]
#[             ]
#[0  0  0  1  0]
#[             ]
#[0  0  0  0  0]
于 2016-05-03T22:13:02.700 に答える