¿Cómo encontrar qué subconjunto de bitfields xor a otro bitfield?

Question

Tengo un problema un tanto matemático orientado. Tengo un montón de bitfields y me gustaría calcular qué subconjunto de ellos se unen para lograr un cierto otro campo de bits, o si no hay una manera de hacerlo, descubro que no existe ese subconjunto.

Me gustaría hacer esto utilizando una biblioteca gratuita, en lugar de código original, y preferiría algo con enlaces de Python (también sería aceptable usar las bibliotecas matemáticas integradas de Python, pero quiero hacer un puerto esto a múltiples idiomas eventualmente). También sería bueno no tomar el golpe de memoria de tener que expandir cada bit a su propio byte.

Algunas aclaraciones adicionales: solo necesito una solución única. Mis matrices son lo opuesto a disperso. Estoy muy interesado en mantener el tiempo de ejecución a un mínimo absoluto, por lo que es muy recomendable utilizar métodos algorítmicamente sofisticados para invertir matrices. Además, es muy importante que el campo de bits específico sea el que se genera, por lo que una técnica que solo encuentre un subconjunto que xor a 0 no lo corte del todo.

Y generalmente conozco la eliminación gaussiana. ¡Estoy tratando de evitar hacer esto desde cero!

cruzada publicado a mathoverflow, porque no es claro cuál es el lugar adecuado para esta pregunta es - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

Answer 1

Matemáticamente hablando, XOR de dos bits puede ser tratado como adición en F_2 campo.

Quiere resolver un conjunto de ecuaciones en un campo F_2. Para cuatro bitfiels con bits (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n), usted obtiene ecuaciones:

x * a_0 + y * b_0 + z * c_0 = r_0 
x * a_1 + y * b_1 + z * c_1 = r_1 
... 
x * a_n + y * b_n + z * c_n = r_n 

(donde busca x, y, z).

Puede programar esto como un problema lineal entero simple con glpk, probablemente lp_solve (pero no recuerdo si encajará). Sin embargo, esto podría funcionar muy lentamente, ya que están tratando de resolver un problema mucho más general.

Después de buscar en Google por un tiempo, parece que este page podría ser un buen comienzo para buscar el código. De las descripciones parece que Dixon y LinBox podrían ser una buena opción.

De todos modos, creo que preguntar en mathoverflow podría darte respuestas más precisas. Si lo hace, por favor enlace su pregunta aquí.

Actualización:Sagemath utiliza M4RI para resolver este problema. Esto hace que (para mí) sea una muy buena recomendación.

Answer 2

Para instancias pequeñas que se ajustan fácilmente en la memoria, esto es solo resolver un sistema lineal sobre F_2, así que intente la eliminación gaussiana de mod-2. Para instancias dispersas muy grandes, como las que ocurren en los algoritmos de factoring (tamiz), busque el algoritmo de Wiedemann.

Answer 3

Es posible tener múltiples subconjuntos xor al mismo valor; ¿te importa encontrar todos los subconjuntos?

Un enfoque quizás de mano dura sería filtrar el powerset de los campos de bits. En Haskell:

import Data.Bits 

xorsTo :: Int -> [Int] -> [[Int]] 
xorsTo target fields = filter xorsToTarget (powerset fields) 
    where xorsToTarget f = (foldl xor 0 f) == target 

powerset [] = [[]] 
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) 

No estoy seguro si hay una manera de hacer esto sin generar el powerset.(En el peor de los casos, es posible que la solución sea realmente el conjunto completo).

Answer 4

la expansión en la respuesta de Liori anterior tenemos un sistema lineal de ecuaciones (en módulo 2):

a0, b0, c0 ...| r0 
a1, b1, c1 ...| r1 
...   | 
an, bn, cn ...| rn 

eliminación de Gauss se puede utilizar para resolver el sistema. En el módulo 2, la operación agregar fila se convierte en una operación XOR. Es mucho más simple computacionalmente hacer esto que usar un solucionador genérico de sistemas lineales.

Entonces, si a0 es cero intercambiamos una fila que tiene un 1 en la posición a. Luego realice un XOR (usando la fila 0) en cualquier otra fila cuyo "a" sea un 1. Luego repita usando la fila 1 y la columna b, luego la fila 2 colc, etc.

Si obtiene una fila de ceros con un cero distinto de cero en la columna r y luego el subconjunto DNE.