Sympy: resolviendo matrices en un campo finito

Para mi proyecto, necesito resolver para una matriz X dadas matrices Y y K. (XY = K) Los elementos de cada matriz deben ser números enteros módulo una prima aleatoria de 256 bits. Mi primer bash de resolver este problema usó la función mod_inv(n) . El problema con esto es que me estoy quedando sin memoria con matrices de alrededor del tamaño 30. Mi siguiente pensamiento fue realizar la factorización de la matriz, ya que eso podría ser menos pesado en la memoria. Sin embargo, parece que SymPy no contiene un solucionador que pueda encontrar matrices en forma de número. ¿Alguna solución o código hecho por mí mismo que pueda usar?

Matrix clase Matrix sympy soporta sympy modulares. Aquí hay un ejemplo de módulo 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] 

El método rref para encontrar la forma escalonada de filas reducidas admite una palabra clave iszerofunction que indica qué entradas dentro de una matriz deben tratarse como cero. Creo que el uso previsto es para la estabilidad numérica (tratar los números pequeños como cero), pero también lo he usado para la reducción modular.

Aquí hay un ejemplo de módulo 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 ] 

Eso es correcto, excepto que la matriz devuelta por rref[0] todavía tiene 5 en ella y fracciones. Trata esto tomando el mod e interpretando las fracciones como inversos modulares:

 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]