Wie finde ich die Teilmenge der Bitfelder xor zu einem anderen Bitfeld?

Question

Ich habe ein etwas mathematisch orientiertes Problem. Ich habe eine Reihe von Bitfeldern und würde gerne berechnen, welche Teilmenge von ihnen zu xor zusammen ist, um ein bestimmtes anderes Bitfeld zu erreichen, oder, wenn es keine Möglichkeit gibt, es zu entdecken, dass keine solche Teilmenge existiert.

Ich möchte dies mit einer freien Bibliothek, anstatt ursprünglichen Code, und ich würde etwas mit Python-Bindungen bevorzugen (mit Python integrierten Math-Bibliotheken wäre auch akzeptabel, aber ich möchte portieren dies zu mehreren Sprachen schließlich). Außerdem wäre es gut, den Speicher nicht zu nehmen, wenn man jedes Bit auf sein eigenes Byte erweitern möchte.

Einige weitere Klarstellung: Ich brauche nur eine einzige Lösung. Meine Matrizen sind das Gegenteil von spärlich. Ich bin sehr daran interessiert, die Laufzeit auf ein absolutes Minimum zu beschränken, daher ist die Verwendung algorithmisch anspruchsvoller Methoden zum Invertieren von Matrizen sehr zu bevorzugen. Außerdem ist es sehr wichtig, dass das spezifizierte Bitfeld das ausgegebene ist, also eine Technik, die nur eine Teilmenge findet, die xor zu 0 nicht ganz schneidet.

Und ich bin mir im Allgemeinen der Gaussian Beseitigung bewusst. Ich versuche, dies von Grund auf zu vermeiden!

Quer gebucht mathoverflow, weil nicht klar ist, was der richtige Ort für diese Frage ist - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

Answer 1

Mathematisch gesprochen, XOR von zwei Bits kann als Zusatz in F_2 Feld behandelt werden.

Sie möchten einen Satz von Gleichungen in einem F_2-Feld lösen. Für vier Bitfelder mit 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), erhalten Sie Gleichungen:

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 

(wo Sie für x, y, z suchen).

Sie könnten dies als ein einfaches ganzzahliges lineares Problem mit glpk, wahrscheinlich lp_solve programmieren (aber ich erinnere mich nicht, wenn es passt). Diese können jedoch sehr langsam arbeiten, da sie versuchen, ein viel allgemeineres Problem zu lösen.

Nach dem googeln für eine Weile scheint es, dass diese page ein guter Start für die Suche nach Code sein könnte. Aus Beschreibungen scheint es, dass Dixon und LinBox eine gute Passform sein könnten.

Wie auch immer, ich denke, bei mathoverflow fragen könnte Ihnen genauere Antworten geben. Wenn ja, verlinke deine Frage bitte hier.

Aktualisierung:Sagemath verwendet M4RI zur Lösung dieses Problems. Dies macht es (für mich) zu einer sehr guten Empfehlung.

Answer 2

Für kleine Instanzen, die leicht in den Speicher passen, löst dies nur ein lineares System über F_2, also versuchen Sie die Mod-2-Gaußsche Eliminierung. Für sehr große Sparse-Instanzen, wie sie in Factoring- (Sieb-) Algorithmen vorkommen, suchen Sie den Wiedemann-Algorithmus.

Answer 3

Es ist möglich, mehrere Teilmengen xor auf denselben Wert zu setzen; interessiert es dich, alle Teilmengen zu finden?

Ein vielleicht schwerfälliger Ansatz wäre es, das Powerset von Bitfeldern zu filtern. In 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) 

Nicht sicher, ob es einen Weg gibt, dies zu tun, ohne das Powerset zu erzeugen.(Im schlimmsten Fall ist es möglich, dass die Lösung tatsächlich das gesamte Powerset ist).

Answer 4

auf Liori Antwort erweitert oben wir ein lineares Gleichungssystem (in Modulo 2):

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

Gauß-Elimination kann das System zu lösen verwendet werden. In Modulo 2 wird die Additionszeilenoperation zu einer XOR-Operation. Es ist viel einfacher, dies rechnerisch zu tun, als einen generischen linearen Systemlöser zu verwenden.

Also, wenn a0 ist Null wir tauschen eine Zeile, die eine 1 in der a-Position hat. Dann führe ein XOR (mit Zeile 0) in jeder anderen Zeile aus, in der "a" ein Bit 1 ist. Wiederhole dann Zeile 1 und Spalte b, dann Zeile 2 Spalte usw.

Wenn du eine Zeile Nullen bekommst mit einer Nicht-Null in der r-Spalte dann die Teilmenge DNE.