Boolean function is an indispensable tool in the process of password system design and analysis. The question of determining whether two Boolean functions are isomorphic has wide needs in the application of Boolean functions. But it is a NP-hard problem and difficult to achieve through taking exhaustive method with increasing variable number and high time complexity. An algorithm of determining Boolean function isomorphism based on ROBDD (reduced ordered binary decision diagram) is put forward. Its complexity depends on time complexity and space complexity of unknown variables' optimal serial algorithm. The proposed algorithm' s time complexity is O(n23n), space complexity is O(3n/(√n)).%布尔函数是密码体制设计与分析中一个不可缺少的工具,在布尔函数的应用中,判定两个布尔函数的同构问题具有广泛的需求,但是,判定布尔函数同构是NP-难问题,并且采取穷举法也将随着变量的增多,因极高的时间复杂度而使其难以实现.该文基于图的思想,提出了一种基于ROBDD(简化有序二元决策图)的布尔函数同构判定算法,其算法的复杂度取决于求解变量的最优编序算法的时间复杂度和空间复杂度,笔者采用的算法时间复杂度为O(n23n),空间复杂度为O(3n/(√n)).
展开▼
