On the Number of Roots of Boolean Polynomials


如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

This paper continues the series of studies of Boolean polynomials (Zhegalkin polynomials or algebraic normal forms (ANFs)). The investigation of properties of Boolean polynomials is an important topic of discrete mathematics and combinatorial analysis. Theoretical results in this field have wide practical applications. For example, a number of popular public-key cryptosystems are based on Reed–Muller codes, and the representation of these codes, as well as encryption and decryption algorithms are based on Boolean polynomials. The spectral properties of such codes are determined by the number of zeros of Boolean polynomials and are analyzed using the randomization lemma. Since the problem of determining the number of zeros Zg of the Boolean polynomial g(x) is NP-hard, the algorithms taking into account the “combinatorial structure of the polynomial” (even though they are search algorithms) are of practical interest. In this paper, such an algorithm based on the properties of the monomial matrix is proposed. For various types of polynomials, exact formulas for the number of roots and the expectation of the number of roots are obtained. A subclass of Boolean polynomials consisting of polynomials with separating variables is considered. A result that can be considered as a generalization of the randomization lemma is proved. The theoretical results provide a basis for estimating the applicability of polynomials for solving various practical problems.

作者简介

V. Leont’ev

Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control,”
Russian Academy of Sciences

编辑信件的主要联系方式.
Email: vkleontiev@yandex.ru
俄罗斯联邦, Moscow, 119333

E. Gordeev

Bauman State Technical University

编辑信件的主要联系方式.
Email: werhorn@yandex.ru
俄罗斯联邦, Moscow, 105005

补充文件

附件文件
动作
1. JATS XML

版权所有 © Pleiades Publishing, Ltd., 2018