Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)8381Research ArticlePresentation of Boolean Polynomials as ZDD-DiagramsFokinP Vfokinpv@gmail.comBlinkovYu AMechanics and Mathematics Departmentblinkovua@info.sgu.ruROSA CompanySaratov State University named after N.G. Chernyshevsky15022014230130508092016Copyright © 2014,2014Boolean Gr¨obner basis have shown their practical efficiency for different problems. Among them are algebraic cryptanalysis HFE (Hidden Field Equations), modeling of quantum computing and boolean satisfiability problem (SAT). Algorithms for computing Gr¨obner basis have exponential complexity for execution time as well as for memory usage. The more appropriate data structure was introduced, which is based on zero-suppressed binary decision diagrams (ZDD). Also we show the relation between ZDD and special recursive notation of polynomials. The recursive notation is the collection of equalities which have had one-to-one correspondence with graphical presentation of ZDDs. We prove lemma which gives the number of nodes estimation for ZDD which represent boolean polynomial with all monoms up to d degree of n variables. Furthermore, we present C++11 ZDD package providing possibility for addition and multiplication of boolean polynomials, multiplication by variable, presentation in compressed recursive form and graphical presentation. The package includes its own implementation of red-black trees, lists, and memory manager. ZDD package was developed for using as internal data structure of the boolean polynomials for computation of involutive Gr¨obner basis.boolean polynomialsbinary decision diagramGr¨obner basisSATбулевы многочленыбинарная диаграмма решенийбазис Грёбнеразадача «Выполнимость»[Lee C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal. - 1959. - Vol. 38. - Pp. 985-999.][Minato S.-I. Zero-Suppressed bdds for Set Manipulation in Combinatorial Problems // Design Automation, 1993. 30th Conference on. - 1993. - Pp. 272-277.][Motter D. B., Roy J. A., Markov I. L. Resolution Cannot Polynomially Simulate Compressed-BFS // Annals of Mathematics and Artificial Intelligence. - 2005. - Vol. 44, No 1-2. - Pp. 121-156.][Gerdt V. P., Zinin M. V., Blinkov Y. A. On Computation of Boolean Involutive Bases // Programming and Computing Software. - 2010. - Vol. 36, No 2. - Pp. 117-123.]