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

• 作者: 李红燕 高飞
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 布尔函数 同构 简化有序二元决策图(ROBDD) 判定算法
• 年，卷（期）: 2011,（6）
• 所属期刊栏目: 信息安全技术
• 页码范围: 1938-1941
• 分类号: TP309
• 字数: 5260字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高飞	解放军信息工程大学电子技术学院	11	29	4.0	4.0
2	李红燕	上海第二工业大学人文学院	7	43	3.0	6.0