基于ROBDD的布尔函数同构判定算法研究

摘要：

布尔函数是密码体制设计与分析中一个不可缺少的工具,在布尔函数的应用中,判定两个布尔函数的同构问题具有广泛的需求,但是,判定布尔函数同构是NP-难问题,并且采取穷举法也将随着变量的增多,因极高的时间复杂度而使其难以实现.该文基于图的思想,提出了一种基于ROBDD(简化有序二元决策图)的布尔函数同构判定算法,其算法的复杂度取决于求解变量的最优编序算法的时间复杂度和空间复杂度,笔者采用的算法时间复杂度为O(n23n),空间复杂度为O(3n/(√n)).

关键词：布尔函数、同构、简化有序二元决策图(ROBDD)、判定算法

所属期刊栏目：32

分类号：TP309(计算技术、计算机技术)

在线出版日期：2011-10-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1938-1941