Sympy：在有限域中求解矩阵

Question

对于我的项目，我需要为给定矩阵Y和K的矩阵X求解。（XY = K）每个矩阵的元素必须是整数模，随机的256位素数。我第一次尝试解决这个问题时使用了SymPy的mod_inv(n)函数。与此相关的问题是我的记忆力不足，大小为30的矩阵。我的下一个想法是执行矩阵因式分解，因为这可能不太重。但是，SymPy似乎不包含可以找到矩阵模数的求解器。我可以使用任何解决方法或自制代码？

Answer 1

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个在它和分数。通过将模块和解释分数作为模块反转来处理此问题：

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]