Алгоритм поиска аффинных аннигиляторов булевой функции
Задача нахождения аннигиляторов низкой степени для произвольной булевой функции до сих пор не имеет эффективных алгоритмов решения. Настоящая работа посвящена предложенному нами алгоритму поиска аффинных аннигиляторов для произвольной булевой функции. Построение нашего алгоритма мы начинаем с исследования тождества fg ≡ 0 для произвольной булевой функции f и ее предполагаемого аффинного аннигилятора g . А именно, мы используем разложение по первой переменной функций f и g для перехода к уравнениям с булевыми функциям от меньшего числа переменных. По сути, мы устанавливаем эквивалентность между тождеством fg ≡ 0 для булевых функций от n переменных и системой уравнений, содержащей булевы функции от n-1 переменной.Алгоритм поиска аффинных аннигиляторов булевой функции f находит все такие аффинные функции g , что fg ≡ 0. Предложенный нами алгоритм основан на сведении задачи нахождения базиса пространства аффинных аннигиляторов для булевой функции от переменных к той же самой задаче для двух ее подфункций от n-1 переменной. У разработанного нами алгоритма можно выделить следующие преимущества:Алгоритм способен принимать входную функцию в различных представлениях;Выходные функции также могут иметь различные представления;Алгоритм может быть эффективно распараллелен.Отметим, что полученный нами результат не является конечным и имеет несколько направлений для развития, среди которых мы отдельно выделим, во-первых, изучение влияния на работу алгоритма различных представлений его входа и выхода и, во-вторых, использование идеи построения нашего алгоритма для разработки алгоритмов поиска аннигиляторов второй, третьей и т.д. степеней для заданной булевой функции.