寻找布尔函数低次零化子的算法

Algorithms of Finding Low Degree Annihilators of Boolean unctions

文章给出了寻找布尔函数低次零化子的几个算法。在分析布尔函数的代数次数与特征矩阵关系的基础上,算法利用布尔函数与其零化子的取值关系来寻找其低次零化子。利用这些算法可以得到布尔函数的所有低次零化子,也可用到其中若干个,利用算法1还可以计算任意一个布尔函数的代数免疫度。

Several algorithms of finding lower degree annihilators of Boolean function are described in this paper. On the basis of analyzing the relationship of algebraic degree and characteristic matrix of Boolean function, and by making use of the support sets of Boolean function and its annihilators, the algorithms get lower degree annihilators of Boolean functions. By these algorithms, one can get all or several annihilators. The algebraic immunity of Boolean functions can be computed by algorithm 1.