Sympy: risoluzione di matrici in un campo finito

Question

Per il mio progetto, ho bisogno di risolvere per una matrice X data le matrici Y e K. (XY = K) Gli elementi di ciascuna matrice devono essere numeri interi formano un primo 256 bit casuale. Il mio primo tentativo di risolvere questo problema ha utilizzato la funzione mod_inv(n) di SymPy. Il problema con questo è che sto esaurendo la memoria con matrici di circa 30. Il mio prossimo pensiero è stato quello di eseguire la fattorizzazione della matrice, in quanto potrebbe essere meno pesante sulla memoria. Tuttavia, SymPy sembra non contenere un solutore in grado di trovare le matrici modulo un numero. Qualche soluzione alternativa o codice auto-fatto che potrei usare?

Answer 1

sympy La classe Matrix supporta gli inversori modulari. Ecco un esempio 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] 

Procedimento rref per reperire forma a scala ridotta per righe supporta una parola iszerofunction che indica quali ingressi all'interno di una matrice deve essere trattato come zero. Credo che l'uso previsto sia per la stabilità numerica (trattare i numeri piccoli come zero), ma l'ho anche usato per la riduzione modulare.

Ecco un esempio 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 ] 

Questo è sorta di correttezza, tranne che la matrice restituita da rref[0] trovi ancora 5 è in esso e frazioni. Affrontalo prendendo le mod e interpretando le frazioni come inversori modulari:

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]