用于对任意变量的两个布尔函数进行仿射等价的判定方法

摘要

本发明公开了一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，属于数字集成电路与密码学领域，其包括以下步骤：一、确定布尔函数F_m；二、任意两个布尔函数，求出对应的变量取值矩阵；三、计算rank(A_f)、rank(Ag);四、判断rank(A_f)、rank(Ag)是否相等，代表元是否相同，若是f与g仿射等价；否则f与g仿射不等价。本发明可以应用到组合逻辑电路、FPGA的可编程逻辑单元和Reed-Muller码中。

主权项

一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，其特征在于，包括以下步骤：一、将布尔函数按照其真值表中包含不同个数1进行分类研究；二、对含有m个1的布尔函数，记为F_m，对使f取值为1所对应的变量取值构成F₂上的矩阵A，即：A(i)＝(x₁,x₂,…,x_n)，其中：f(x₁,x₂,…,x_n)＝1。三、对任意两个布尔函数f,g∈F_m，求出对应的变量取值矩阵A_f、A_g，若f与g仿射等价，则rank(A_f)＝rank(A_g)＝r；反之，若rank(A_f)≠rank(A_g)，则f与g必然仿射不等价。四、求出不同类布尔函数对应的变量取值矩阵A；五、将矩阵A进行一系列初等列变换如对列进行取非、把其中一列加到任意一列、两列之间的交换，找出该类仿射等价类的代表元。