|
This article is cited in 4 scientific papers (total in 4 papers)
An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial
V. V. Baev
Abstract:
A Boolean function $g$ is said to be an annihilator of a Boolean function $f$ if $fg=0$. In some problems concerning finite automata, it is required to find non-zero annihilators of low algebraic degree for a function $f$.
In this paper we suggest Algorithm M2 which, given the Zhegalkin polynomial for a function $f$, yields a basis of the space of its annihilators of degree not exceeding $d$. Algorithm M2 is an enhancement of a previously known algorithm and allows in a series of cases to decrease calculations. The total complexity of Algorithm M2 is the same as for the previous algorithm.
Received: 18.05.2007
Citation:
V. V. Baev, “An enhanced algorithm to search for low-degree annihilators for a Zhegalkin polynomial”, Diskr. Mat., 19:4 (2007), 132–138; Discrete Math. Appl., 17:5 (2007), 533–538
Linking options:
https://www.mathnet.ru/eng/dm982https://doi.org/10.4213/dm982 https://www.mathnet.ru/eng/dm/v19/i4/p132
|
Statistics & downloads: |
Abstract page: | 719 | Full-text PDF : | 315 | References: | 58 | First page: | 8 |
|