О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций

Алгебраический метод широко используется при анализе фильтрующих генераторов псевдослучайных последовательностей. Он основан на получении булевых уравнений низкой степени относительно битов начального состояния генератора. Задача получения таких уравнений сводится к поиску обнуляющих множителей (аннигиляторов) низкой степени для фильтрующей булевой функции. Наличие ненулевых низкостепенных аннигиляторов снижает сложность определения начального состояния генератора по его выходной последовательности.
В работе исследуется задача нахождения всех низкостепенных аннигиляторов для булевой функции, заданной в виде многочлена от нескольких переменных. Предлагаются два новых алгоритма решения этой задачи. Их сложности оцениваются сверху полиномами от количества переменных функции и от количества мономов в многочлене, который задает эту функцию. Рассмотрено также применение этих алгоритмов для реализации алгебраического метода по трем известным сценариям, в соответствии с которыми получаются уравнения низкой степени.