Sympy:在有限域中求解矩阵 [英] Sympy: Solving Matrices in a finite field

问题描述

对于我的项目，我需要在给定矩阵Y和K的情况下求解矩阵X.(XY = K)每个矩阵的元素必须是对256位随机质数求模的整数.解决这个问题的第一个尝试是使用SymPy的mod_inv(n)函数.问题是我的矩阵大小为30的内存用完了.我的下一个想法是执行矩阵分解，因为这样可能减轻了内存的负担.但是，SymPy似乎不包含能够找到以模为模的矩阵的求解器.我可以使用任何解决方法或自制代码吗?

For my project, I need to solve for a matrix X given matrices Y and K. (XY=K) The elements of each matrix must be integers modulo a random 256-bit prime. My first attempt at solving this problem used SymPy's mod_inv(n) function. The problem with this is that I'm running out of memory with matrices of around size 30. My next thought was to perform matrix factorization, as that might be less heavy on memory. However, SymPy seems to contain no solver that can find matrices modulo a number. Any workarounds or self-made code I could use?

推荐答案

sympy的Matrix类支持模块化逆.这是模5的示例:

sympy's Matrix class supports modular inverses. Here's an example modulo 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，该关键字指示矩阵中的哪些条目应被视为零.我相信预期用途是为了保持数值稳定性(将小数设为零)，但我也将其用于模数归约.

The rref method for finding row-reduced echelon form supports a keyword iszerofunction that indicates what entries within a matrix should be treated as zero. I believe the intended use is for numerical stability (treat small numbers as zero), but I have also used it for modular reduction.

以下是模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并将分数解释为模逆来解决此问题:

That's sort of correct, except that the matrix returned by rref[0] still has 5's in it and fractions. Deal with this by taking the mod and interpreting fractions as modular inverses:

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]

这篇关于Sympy:在有限域中求解矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！