Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm |
| |
Authors: | K N Koryagin |
| |
Institution: | 1.Dorodnicyn Computing Center,Russian Academy of Sciences,Moscow,Russia |
| |
Abstract: | Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin
polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding
all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology.
In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations.
Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm
makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does
not reduce the asymptotic complexity of solving systems of linear Boolean equations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|