布尔函数的代数免疫度分层

摘要

布尔函数的代数免疫度是在对流密码的代数攻击中产生的新概念,对任意n元布尔函数,其代数免疫度AI<,n>(f)可取值{0,1,…,[n/2]},对其中任意k,记B<,n,k>为代数免疫度为k的布尔函数全体,我们知道B<,n,k>总是非空,根据代数免疫度我们可以对布尔函数进行分层。|B<,n,0>|=2是平凡的,但一般地,关于整数序列|B<,n,k>|,k=1,……,[n/2]结果不多。本文给出了|B<,n,0>|的明确公式,这是关于该序列的第一个精确公式,并且我们得到了一个关于代数免疫度为1的布尔函数的非线性度的紧的上界。