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?Sympy: risoluzione di matrici in un campo finito
6
A
risposta
5
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]
Problemi correlati
- 1. Sistemi Risoluzione di equazioni con SymPy
- 2. Miglioramento dell'algoritmo di risoluzione del campo minato
- 3. Come espandere l'espressione di matrice in sympy
- 4. Sostituzione ricorsiva in sympy
- 5. Test se la matrice è invertibile su campo finito
- 6. Automa finito in Haskell
- 7. Ignora radici immaginarie in sympy
- 8. sostituzione non sequenziale in SymPy
- 9. Eigenvector non funziona in Sympy
- 10. Tabelle di verità in python usando sympy
- 11. SymPy - Numero arbitrario di simboli
- 12. Inversa di una matrice in SymPy?
- 13. Che cos'è un trasduttore di stato finito?
- 14. Archiviazione di matrici annidate in un cookie
- 15. Matrici di trasposizione in un array
- 16. Disegnare con SymPy
- 17. Combinando NumPy con sympy
- 18. Sympy second order ode
- 19. sympy: l'oggetto 'Transpose' non ha attributo tolist
- 20. Sympy - Confronto espressioni
- 21. SymPy: Scambia due variabili
- 22. Sympy: integrated() output strano
- 23. Progetti che utilizzano SymPy?
- 24. Elenco di matrici in Java
- 25. Come posso ottenere un elenco dei simboli in un'espressione sympy?
- 26. Matrici di stampa in Java
- 27. Potenze algebriche espandibili in python (sympy)
- 28. Come semplificare le espressioni sqrt in sympy
- 29. Matrici ALLOCATABLE o matrici POINTER?
- 30. Confronto di matrici in C#
NB: questa funzione non funziona sempre. Un esempio è Matrix ([[4,3,1,3], [2,4,1,3]]) in Z_5. In questo caso, la normale chiamata iszerofunc usando lambda x: x% 5 == 0 fornisce una matrice con denominatori incluso un 5. Poiché in Z_5 non c'è inverso per 5, il programma uscirà. – brunston