雷竞技网页版研究和评论——国际期刊雷竞技苹果下载

国际先进研究期刊》的研究在电子、电子、仪表工程

菜单

ISSN在线(2278 - 8875)打印(2320 - 3765)

所有提交的电磁系统将被重定向到在线手稿提交系统。作者请直接提交文章在线手稿提交系统各自的杂志。

算法来确定固定多项式密码学的布尔函数

阮Huu同庆铁男
讲师,电气和电子工程部门,吨Duc Thang大学越南胡志明市
相关文章Pubmed,谷歌学者

访问更多的相关文章国际先进研究期刊》的研究在电子、电子、仪表工程

国际先进研究期刊》的研究在电子、电子、仪表工程

文摘

每一个布尔函数是唯一地定义为一个多项式模2。一个布尔函数的程度是其定义多项式的程度。在密码学中,布尔函数的固定程度扮演了重要的角色,例如,1或2度。因此,在发现算法,识别属性的布尔函数多项式的值向量,是有道理的只考虑较低的算法复杂度。在本文中,我们提出一个线性复杂度的算法决定了布尔函数向量的值,这是一个多项式的固定程度,如果是构建这个多项式。

关键字
布尔函数、固定多项式代数范式、数值正常形式

介绍
矢量加密之前,布尔函数集合{0,1}将通常具有的结构字段(用F2),和F2n集的二进制向量长度为n的将被视为一个F2 - vectorspace。我们将表示只需在F2n 0零向量。的vectorspace F2n有时会也赋予了字段的结构{领域F2n(也用GF (2 n)) [1];的确,这一领域作为一个n维vectorspace F2,它的每个元素可以被识别的二进制向量长度n的坐标相对于一个固定的基础。所有布尔函数f: F2n - > F2将由BFn表示像往常一样。汉明重量wH (x)的一个二进制向量xεF2n非零的数字坐标,汉明重量wH的布尔函数f (f) F2n支持功能的大小,即集合{xεF2n / f (x)≠0}。之间的汉明距离dH (f, g)两个函数f和g大小的设置{xεF2n / f (x)≠g (x)}。因此它等于wH (fΘg)。
添加的部分将被认为是在Z(0)特点和表示+,有时会计算模2和用Θ。这两个dierent符号将是必要的,因为布尔函数的一些表示将生活在特征2和一些表示相同的函数将生活在特征0。但有限域的元素的添加F2n将用+,因为它是通常的数学。所以,为简单起见(因为F2n常常被标识F2n)因为没有歧义,我们还应当表示+向量的加法F2n当n > 1。
许多结构与属性相关的密码学布尔函数的递归(2、4、5)。结构的效率在很大程度上依赖于适当的使用小尺寸的函数。另一个重要的施工方法是随机启发式搜索方法[2,3]。等价类是用来提供限制输入的优化算法,它是非常重要的识别等价类获取函数所需的属性。方法边界多项式的程度,现在的布尔函数复杂性理论的重要工具。这些技术已经被用来获得一些结果,阐明复杂的布尔函数。特别是,多项式程度constant-depth电路复杂度的下界后果相关的布尔函数。
让布尔函数写向量与N = 2 N的值坐标,其中N -数量的变量的函数。众所周知,一个布尔函数的值向量可以找到一个多项式复杂性的O (N logN) [7]。因此,在发现算法,识别属性的布尔函数多项式的值向量,是有道理的只考虑低阶的复杂性的算法。在本文中,我们提出一个线性复杂度的算法决定了布尔函数向量的值,这是一个多项式的固定程度,如果是构建这个多项式。

布尔函数的代表
在经典的布尔函数的表征,这是一个最通常用于加密和编码在F2 n变量多项式表示,的形式:
图像(1)
P (N)表示的幂集N = {1,…, N}。每个坐标xi出现在这个多项式指数最多1,因为在F2 =自己的广场。这种表示方法属于图像。它被称为代数范式(总之曾帮工)。
另一个可能的表示这个曾帮工使用指数化的向量F2n代替N的子集;对于任何此类向量u,我们表示,非盟是什么用asupp (u)的关系(1)(增刊)(u)表示你的支持,我们有等效表示:
图像(2)
的单项图像通常是用徐。
2.1。一个布尔函数及其之间的关系曾帮工。
该产品图像非零当且仅当xi是零(即等于1)每我ε,也就是说,如果我是包含在x的支持;因此,布尔函数图像需要的价值。
图像
在增刊(x)表示x的支持。如果我们使用符号吗图像我们获得的关系图像在u≤x意味着增刊(u)⊆增刊(x)(我们说你是由x)。一个布尔函数f 0可以联系到f的曾帮工:对于每一个吗图像也就是说,与符号图像关系(3)表明,f f的形象由所谓的二进制0莫比乌斯变换。
反过来也是如此:
命题1:让f F2n,让布尔函数图像曾帮工。我们有:
图像(4)
证明。让我们表示图像由bI和考虑的功能图像我们有
图像
因此
图像
之和图像是null如果y≠x,因为集合{我εP (N) /增刊(y)⊆我⊆增刊(x)}包含吗图像元素如果增刊(y)⊆增刊(x),否则,没有。因此,g = f,曾帮工的独特性,bI =每我aI。
2.2。曾帮工的程度。
它用d0f称为函数的代数程度(这有意义的存在性和唯一性曾帮工):图像我在哪里| |表示。一些作者的大小也称之为非线性f。根据关系(4),我们有:
命题2:n变量的代数学位d0f布尔函数f等于最大的子空间的维数图像的f值1奇数倍。
代数程度是一个仿射不变量(一般仿射不变的作用下组):每一个仿射同构李:
图像
(M是一个非奇异的n * n矩阵/ F2)。我们有d0 (f L o) = d0f。事实上,组成由L显然不能增加代数程度,因为L (x)的坐标有学位1。因此我们有d0 (f L o)≤d0f(这个不等式更广泛有效的对每一个仿射同态)。和应用这种不平等在f和f L o L - 1 L的地方如何逆不等式。两个函数f和f L, L是一个阿F2 -线性自同构F2n (a1, a2 =…= = 0以上)将被称为线性等效和两个函数f和f o L, L是一个仿射F2n自同构,必称为仿射等价的。
代数程度作为一个仿射不变量,命题2意味着它还等于所有的仿射子空间的最大尺寸的F2n f值1奇数倍。

表示在实数
布尔函数证明了自己是用于描述一些加密标准(8、9)。它代表了布尔函数和更一般的实值函数F2n(也被称为n变量pseudo-Boolean函数)的元素整数值函数)。我们叫它数值范式(NNF)。
这对每个pseudo-Boolean函数表示的存在很容易显示相同的参数作为曾帮工的布尔函数(写1 - xi代替图像)。每一个元素的线性映射的2 n - th维F2n vectorspace图像F2n对应的pseudo-Boolean函数,因此,一对一(F2n——vectorspace F2n pseudo-Boolean功能也有尺寸2 n)。我们推断NNF的独特性。
我们所说的程度函数的NNF数值学位。由于曾帮工是国防部2版本的NNF,数值上总是有下界的代数的学位。[4]所示,如果一个布尔函数f没有无效的变量(即如果这实际上取决于它的每个变量),然后f的数值程度大于或等于图像
数值程度不是一个仿射不变量。但NNF导致一个仿射不变(见[8]证明这个事实;参见[10]),比代数程度判别:
Denition 1:让f是一个布尔函数F2n我们称之为广义f度序列di(≥1)定义如下:对于每个≥1,di是最小的整数di > di-1(如果我> 1),每多索引的大小严格大于d, f的系数ξ的λI NNF我是2的倍数。
例子:任何非零一函数的广义程度是所有正整数序列。同样对于曾帮工,(伪)布尔函数图像需要的值:
但是,相反我们观察到曾帮工,相反的公式是不相同的直接公式:命题3:让f F2n pseudo-Boolean功能,让其NNF图像。然后:
图像(6)
因此,相关函数及其NNF通过默比乌斯变换整数。
证明。让我们表示数量图像
考虑到功能图像
图像
之和图像是null如果增刊(y)⊆增刊(x)。也是null如果增刊(y)包含在增刊(x),但不同。事实上,表示我| | - wH (y),它等于
图像
因此,g = f, NNF的独特性,我们μI =λI每一个我。
命题4:任何多项式图像是一个整数值函数的NNF当且仅当所有的系数都是整数。假设这种情况是satisffied P的NNF布尔函数当且仅当:图像
证明。第一个断言是一个直接后果的关系(5)和(6)。如果所有的系数P是整数,然后我们有图像对于每一个x;这意味着2 n平等,表达相应的布尔函数,可以减少到一个图像
让图像——设置长度为n的向量的坐标设置布尔函数是一个映射。
图像
所有布尔函数根据n变量的集合,表示当n F。
单调小学一起被称为不同的变量没有否定的产物。单调的排名基本是变量的数量。我们假设一个退化单调小学连词级别0。每一个布尔函数可以写独特的形式习——不同的单调小学连词,求和是国防部2。多项式的次数是最大的排名。我们说一个函数f (x1,…,xn) belongs to the class Cm, m = 0, 1, 2, ..., if it is given a polynomial of degree m. Obviously, the class C0 only contains constants 0 and 1, class C1 is the class L of linear functions. We call the derivative of f (x1, ..., xn) with respect to xi function fxi (x1, ..., xn), equal
图像
定理1。函数f (x1,…,xn) belongs to the class Cm, m> 1, if and only if for each variable xi, i = 1, ... , n, function fxi (x1, ..., xn) belongs to Cm-1.
证明。遵循从导数的定义和独特的布尔函数的多项式表示。让布尔函数f (x1,…,xn) is given a vector of its values αf on the sets listed in lexicographic order. The number of coordinates αf equal to N = 2n.
定理2。存在一个算法复杂度O (N)的向量αf决定函数f (x1,…xn)是线性的,如果是这样,它构建一个多项式。证明。考虑下面的算法。
我:= 1;
fi (xi,…。,xn) := f (x1, …., xn);
p (xi,…。,xn) := f (0, …., 0).
周期的开始。
1。建立一个导数fiξ(ξ,……,xn): divide the vector αf i in two and summarize the coordinate-wise. At the same time will be spent 2n-i+1 operations.
2。如果
•中国股市基金(xi,…,xn) ≡ 1, then p (x1, ..., xn): = p (xi, ..., xn) ⊕ xi;
•中国股市基金(xi,…,xn) ≡ 0, then p (x1, ..., xn) remain unchanged;
•否则——算法终止和答案是“非线性函数,线性。
3所示。我= + 1,fi (xi,…,xn) = fi-1 (0, xi, ..., xn),. To construct a vector αf i requires 2n-i+1 operations.
4所示。如果
•我> n,则算法终止,答案是“线性函数”,它是写在多项式p (x1,…,xn);
•否则——去循环的顶部。
算法的正确性遵循从定理1。
我们计算算法的复杂性。它是
图像
定理3。分配一个号码m > 1。存在一个向量αf算法复杂度O (N)确定一个函数f (x1,…类xn)厘米,如果是这样,它构建一个多项式。
证明。我们构建所需的算法是电感。归纳的基础。让m = 1。然后,当算法A1将考虑定理2中描述的算法。其复杂性等于2。2 n。
归纳步骤。假设算法Am-1已经构造,其复杂性等于cm - 1。2 n, cm - 1——是一个常数。我考虑一个算法如下:
我:= 1;
fi (xi,…。,xn) := f (x1, …., xn);
p (xi,…。,xn) := f (0, …., 0).
周期的开始。
1。建立一个导数fiξ(ξ,……,xn): divide the vector αf i in two and summarize the coordinate-wise. At the same time will be spent 2n-i+1 operations.
2。与算法Am-1检查是否函数貌似(xi,…cm - 1 xn)类。
如果
•回答“是的”和一个多项式p (x1,…xn)
图像
•否则,算法终止答案是“功能不属于厘米”。
在步骤2中,我们花了厘米- 1.2 - n - i + 1操作。
3所示。我= + 1,fi (xi,…,xn) = fi-1 (0, xi, ..., xn). For constructing vector αf i requires 2n-i+1 operations.
4所示。如果
•我> n,则算法终止,答案是“厘米”的功能,它是写在多项式P (x1,…,xn);
•否则——去循环的顶部。算法的正确性遵循从定理1。我们计算算法的复杂性。
它是图像在Cm -一个常数。所以图像很容易计算出厘米= 2.2 m。因此,算法的复杂性(2.2米)。2 N = O (N),因为m -固定数量。

结论
在本文中,我们表明,许多传统概念,构造算法识别属性的布尔函数多项式的值向量,是有道理的只考虑较低的算法复杂度。线性复杂度的算法决定了布尔函数向量的值,这是一个多项式的固定程度。这些结果申请密码理论的布尔函数的性质。

引用










全球技术峰会