Jak znaleźć podzbiór bitfields xor na inne bitfield?

Question

Mam pewien problem z matematyką. Mam kilka pól bitowych i chciałbym obliczyć, jaki podzestaw ich użyć, aby uzyskać inne pole bitowe, lub jeśli nie ma sposobu, aby to zrobić, odkryć, że nie istnieje taki podzbiór.

Chciałbym zrobić to za pomocą wolnej biblioteki, a nie oryginalnego kodu, i zdecydowanie wolałbym coś z powiązaniami w Pythonie (używanie wbudowanych bibliotek matematycznych Pythona byłoby również akceptowalne, ale chcę portować w końcu do wielu języków). Poza tym dobrze byłoby nie brać w pamięci trafienia konieczności rozszerzania każdego bitu do własnego bajtu.

Kilka dodatkowych wyjaśnień: Potrzebuję tylko jednego rozwiązania. Moje matryce są przeciwieństwem rzadkości. Jestem bardzo zainteresowany utrzymaniem środowiska wykonawczego na absolutnym minimum, więc zdecydowanie preferowane jest stosowanie algorytmicznych metod odwracania matryc. Ponadto bardzo ważne jest, aby konkretne dane pole bitowe było tym, które zostało wyprowadzone, więc technika, która właśnie znajduje podzbiór, który xor do 0, nie całkiem go wycina.

I ogólnie jestem świadomy gaussowskiej eliminacji. Próbuję tego uniknąć od zera!

cross-wysłana do mathoverflow, ponieważ nie jest jasne, co właściwe miejsce na to pytanie jest - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

Answer 1

Matematycznie rzecz biorąc, XOR dwóch bitów może być traktowana jako dodatek w F_2 dziedzinie.

Chcesz rozwiązać zestaw równań w polu F_2. Dla czterech bitfielów z bitami (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n), otrzymujesz równania:

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 

(gdzie szukasz x, y, z).

Można to zaprogramować jako zwykły prosty liniowy problem z glpk, prawdopodobnie lp_solve (ale nie pamiętam, czy będzie pasować). Mogą one jednak działać bardzo powoli, ponieważ próbują rozwiązać znacznie bardziej ogólny problem.

Po pewnym czasie googlowania wydaje się, że to page może być dobrym początkiem w poszukiwaniu kodu. Z opisu wydaje się, że Dixon i LinBox mogą być dobrze dopasowane.

W każdym razie, myślę, że poproszenie o przepływ przez telefon może dać ci bardziej precyzyjne odpowiedzi. Jeśli tak, proszę połączyć swoje pytanie tutaj.

Aktualizacja:Sagemath używa M4RI do rozwiązania tego problemu. To sprawia, że ​​jest to (dla mnie) bardzo dobra rekomendacja.

Answer 2

Dla małych instancji, które łatwo mieszczą się w pamięci, jest to po prostu rozwiązanie liniowego systemu przez F_2, więc spróbuj mod-2 Gaussian eliminacji. W przypadku bardzo rzadkich instancji, takich jak te występujące w algorytmach faktoringu (sita), wyszukaj algorytm Wiedemanna.

Answer 3

Możliwe jest posiadanie wielu podzbiorów xor do tej samej wartości; czy zależy ci na znalezieniu wszystkich podzbiorów?

Być może podejście z dużą dozą nacisku polegałoby na filtrowaniu zestawu bitów. W 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) 

Nie wiem, czy istnieje sposób, aby to zrobić bez generowania PowerSet.(W najgorszym przypadku rozwiązaniem może być cały zestaw energetyczny).

Answer 4

rozszerza na odpowiedź liori za wyżej mamy system równań liniowych (w modulo 2):

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

eliminacji Gaussa można wykorzystać do rozwiązania układu. W modulo 2 operacja dodawania wiersza staje się operacją XOR. Jest to o wiele prostsze obliczeniowo niż użycie ogólnego rozwiązania solwerów systemów liniowych.

Tak więc, jeśli a0 wynosi zero, zamieniamy rząd, który ma 1 w pozycji. Następnie wykonaj XOR (używając wiersza 0) w dowolnym innym wierszu, w którym bit "a" to 1. Następnie powtórz używając wiersza 1 i kolumny b, następnie wiersza 2 kolumny c, itd.

Jeśli pojawi się rząd zer z niezerową wartością w kolumnie r, a następnie z podzbiorem DNE.