论文标题
快速计算布尔函数代数度的方法
A Method for Fast Computing the Algebraic Degree of Boolean Functions
论文作者
论文摘要
布尔函数（或矢量布尔函数）的代数程度是重要的加密参数，应通过快速算法计算。它们以两种主要方式工作：（1）通过计算代数正常形式，然后搜索其最高程度的单一形式，或者（2）通过检查给定函数的真实表向量的代数特性。我们已经在研究第一个方法的研究中已经完成了四个基本步骤，第二个作者已经研究了第二个步骤。在这里，我们代表了一种快速计算的方法（我们知道的最快方式）布尔函数的代数程度。它是这两种方法中最有效的组件和相应算法的组合。该方法的理论时间复杂性是在每种情况下以字节或比特方式表示布尔函数的情况下得出的。对于$ n $变量的布尔函数，它们具有相同类型的$θ（n.2^n）$，但它们之间的常数差异很大。这里所示的理论和实验结果证明了位方法在计算代数程度方面的优势 - 它们比字节智能方法快几十倍。
The algebraic degree of Boolean functions (or vectorial Boolean functions) is an important cryptographic parameter that should be computed by fast algorithms. They work in two main ways: (1) by computing the algebraic normal form and then searching the monomial of the highest degree in it, or (2) by examination the algebraic properties of the true table vector of a given function. We have already done four basic steps in the study of the first way, and the second one has been studied by other authors. Here we represent a method for fast computing (the fastest way we know) the algebraic degree of Boolean functions. It is a combination of the most efficient components of these two ways and the corresponding algorithms. The theoretical time complexities of the method are derived in each of the cases when the Boolean function is represented in a byte-wise or in a bitwise manner. They are of the same type $Θ(n.2^n)$ for a Boolean function of $n$ variables, but they have big differences between the constants in $Θ$-notation. The theoretical and experimental results shown here demonstrate the advantages of the bitwise approach in computing the algebraic degree - they are dozens of times faster than the byte-wise approaches.
