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]