| 最优代数免疫布尔函数的完全构造 |
|
|
|
定理3 设n为正整数，设f是F2n上的一个平衡布尔函数，其支撑集为{α1,…,α2n－1}，其中αi∈F2n，i=1,…,2n-1。矩阵H如式(3)所示，规模为2n－1×(2n－1)。其列向量分别记为H0,H1,…,H2n－2。令A={0≤i≤2n－2|w2(i)≤「n/2－1}，取H的第i(i∈A)列构成新的矩阵H′=(Hi)i∈A。若矩阵H′非退化，则f没有代数次数<「n/2的零化子。
证明 用反证法证明，若f存在代数次数<「n/2的非零零化子g此句是否应该为“非零化子g”？请对比上下文，作出调整。，其单论文联盟*变元多项式表示为g(x)=∑2n－1i=0gixi，当iA时，gi=0。g的单变元多项式表示可以写为：
g(x)=∑i∈Agixi
则方程组(2)演化为：
∑w2(i)≤「n/2－1Higi=0 H′(gi)Ti∈A=0(6)
注意此时矩阵H中起作用的列向量为(Hi)i∈A。又知g是一个非零的函数，故w((gi)i∈A)>0，即式(6)有非零解。这与已知条件矩阵H′非退化矛盾。故deg(g)<「n/2当且仅当g=0，此时f没有代数次数<「n/2的零化子，即证。这个“#”符号有何作用，是否可以删除，请明确。回复：#表示证明结束。也可以用实心方块表示。最好不要删除。
当n为奇数时，具有最优代数免疫的布尔函数一定是平衡的［5］，若一个平衡布尔函数的单变元多项式表示满足定理2的条件，就具有最优代数免疫。实际上，矩阵H′非退化是奇数元布尔函数代数免疫达到最优的充要条件。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >> |
|
|
| |
|
上一个论文： 用二元一次方程组巧解古代数学名题
下一个论文： 初中代数应用题的审题策略 |
|
用户登录 
新用户注册 