Discrete and Continuous Models and Applied Computational ScienceDiscrete 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)8381ArticlesСтатьиResearch ArticlePresentation of Boolean Polynomials as ZDD-DiagramsПредставление булевых многочленов в виде ZDD-диаграммFokinP VФокинПавел Владимировичfokinpv@gmail.comBlinkovYu AБлинковЮрий АнатольевичMechanics and Mathematics DepartmentМеханико-математический факультетblinkovua@info.sgu.ruROSA CompanyЗАО «РОСА»Saratov State University named after N.G. ChernyshevskyСаратовский государственный университет им. Н.Г. Чернышевского150220142NO2 (2014)№2 (2014)30130508092016Copyright ©; 2014, Фокин П.В., Блинков Ю.А.2014Фокин П.В., Блинков Ю.А.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/miph/article/view/8381Boolean 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.Булевы базисы Грёбнера проявили свою практическую применимость для ряда задач, таких как HFE (Hidden Field Equations) в криптографии, моделирование квантовых вычислений и к задаче «Выполнимость» для конъюнктивной нормальной формы. Алгоритмы построения базисов Грёбнера имеют экспоненциальную сложность построения как по времени выполнения, так и по требуемой памяти. Для более компактного хранения булевых многочленов было предложено использовать ZDD-диаграммы. Показана связь ZDD-диаграмм с специальным видом рекурсивным представлением многочленов, которое отождествляет ZDD-диаграмму с некоторым набором равенств. Доказана лемма дающая число вершин в ZDD-диаграмме для представления булевого многочлена, состоящего из всех мономов до степени d включительно. Представлен пакет на языке C++11 для работы с ZDD-диаграммами. В состав пакета входят собственная реализация красно-чёрных деревьев, списков и менеджера памяти. Пакет разрабатывался для использования как внутреннее представление булевых многочленов, в ней реализованы операции сложения и умножение двух многочленов, а также умножение на переменную, которое используются при построении инволютивных базисов Грёбнера.boolean polynomialsbinary decision diagramGr¨obner basisSATбулевы многочленыбинарная диаграмма решенийбазис Грёбнеразадача «Выполнимость»1.Lee C. Y. Representation of Switching Circuits by Binary-Decision Programs // Bell Systems Technical Journal. - 1959. - Vol. 38. - Pp. 985-999.2.Minato S.-I. Zero-Suppressed bdds for Set Manipulation in Combinatorial Problems // Design Automation, 1993. 30th Conference on. - 1993. - Pp. 272-277.3.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.4.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.