Как найти подмножество битовых полей xor к другому битовому полю?

Question

У меня есть математическая проблема.У меня есть набор битовых полей, и я хотел бы рассчитать, какое их подмножество нужно xor вместе для достижения определенного другого битового поля, или, если нет способа сделать это, обнаружите, что такого подмножества не существует.

IЯ хотел бы сделать это, используя свободную библиотеку, а не оригинальный код, и я бы настоятельно предпочел что-то с привязками Python (использование встроенных математических библиотек Python также было бы приемлемо, но я хочу со временем перенести это на несколько языков).).Кроме того, было бы хорошо, если бы не было необходимости использовать память, чтобы расширить каждый бит до своего собственного байта.

Некоторые дополнительные пояснения: мне нужно только одно решение.Мои матрицы противоположны разреженным.Я очень заинтересован в том, чтобы свести время выполнения к абсолютному минимуму, поэтому настоятельно рекомендуется использовать алгоритмически причудливые методы для инвертирования матриц.Кроме того, очень важно, чтобы конкретное заданное битовое поле было тем, которое выводится, поэтому метод, который просто находит подмножество, значение xor которого равно 0, не совсем его обрезает.Я пытаюсь избежать этого с нуля!

перекрестно опубликовано в mathoverflow, потому что не ясно, каково правильное место для этого вопроса - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

Answer 1

Математически говоря, XOR двух битов может рассматриваться как сложение в поле F_2.

Вы хотите решить набор уравнений в поле F_2.Для четырех битовых полей с битами (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n), вы получите уравнения:

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

(где вы ищете x, y, z).

Вы можете запрограммировать это как простую целочисленную линейную задачу с glpk, возможно lp_solve (но я не помню, подойдет ли это).Однако они могут работать очень медленно, поскольку пытаются решить гораздо более общую проблему.

После некоторого поиска в Google, кажется, эта страница может быть хорошим началом поиска кода.Из описаний видно, что Dixon и LinBox могли бы подойти.

В любом случае, я думаю, что вопрос в mathoverflow может дать вам более точные ответы.Если вы это сделаете, пожалуйста, свяжите ваш вопрос здесь.

Обновление: Sagemath использует M4RI для решения этой проблемы.Это делает его (для меня) очень хорошей рекомендацией.

Answer 2

Для небольших экземпляров, которые легко помещаются в памяти, это просто решение линейной системы над F_2, поэтому попробуйте исключение Гаусса в mod-2.Для очень больших разреженных экземпляров, таких как те, которые встречаются в алгоритмах факторинга (просеивания), ищите алгоритм Видемана.

Answer 3

Возможно иметь несколько подмножеств xor к одному и тому же значению;Вас интересует поиск всех подмножеств?

Возможно, неуклюжий подход заключается в фильтрации набора битовых полей.В 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)

Не уверен, есть ли способ сделать это без генерации powerset.(В худшем случае решение может быть на самом деле всем блоком питания).

Answer 4

, расширяя ответ Лиори, приведенный выше, мы имеем линейную систему уравнений (по модулю 2):

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

Для решения системы можно использовать исключение Гаусса.В модуле 2 операция добавления строки становится операцией XOR.В вычислительном отношении это сделать гораздо проще, чем использовать универсальный решатель линейных систем.

Итак, если a0 равно нулю, мы поменяем строку, в которой есть 1 в позиции a.Затем выполните XOR (используя строку 0) для любой другой строки, чей «a» бит равен 1. Затем повторите, используя строку 1 и столбец b, затем строку 2, столбец c и т. Д.

Если вы получили строкунулей с ненулевым значением в столбце r, а затем подмножество DNE.