Sympy: Giải quyết Ma trận trong trường hữu hạn

Question

Đối với dự án của tôi, tôi cần giải quyết ma trận X cho ma trận Y và K. (XY = K) Các phần tử của mỗi ma trận phải là số nguyên modulo một số nguyên tố 256 bit ngẫu nhiên. Nỗ lực đầu tiên của tôi trong việc giải quyết vấn đề này đã sử dụng chức năng mod_inv(n) của SymPy. Vấn đề với điều này là tôi đang hết bộ nhớ với ma trận khoảng 30. Suy nghĩ tiếp theo của tôi là thực hiện hệ số ma trận, vì điều đó có thể ít nặng hơn trên bộ nhớ. Tuy nhiên, SymPy dường như không chứa bộ giải mã nào có thể tìm thấy ma trận modulo một số. Bất kỳ cách giải quyết nào hoặc mã tự tạo tôi có thể sử dụng?

Answer 1

sympy 's Matrix lớp hỗ trợ inverses mô-đun. Dưới đây là một ví dụ 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] 

Phương pháp rref cho việc tìm kiếm hình thức bậc thang hàng-giảm hỗ trợ từ khóa iszerofunction cho biết những gì các entry trong một ma trận phải được coi là zero. Tôi tin rằng mục đích sử dụng là để ổn định số (xử lý các số nhỏ bằng 0), nhưng tôi cũng đã sử dụng nó để giảm mô-đun.

Dưới đây là một ví dụ modulo 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 ] 

Đó là loại đúng, ngoại trừ việc ma trận được trả về bởi rref[0] vẫn có 5 trong nó và các phần phân đoạn. Giải quyết vấn đề này bằng cách sử dụng công cụ sửa đổi và giải thích các phân số dưới dạng các đầu vào mô-đun:

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]