（中國(guó)電子科技集團(tuán)公司第三十研究所 成都 610041）

1 引言

2 準(zhǔn)備工作

首先給出相關(guān)免疫的概念。

定義1設(shè)f(x1，x2，…，xn)是一個(gè)n元布爾函數(shù)，其中x1，x2，…，xn是均勻分布的獨(dú)立隨機(jī)變量，如果f與x1，x2，…，xn中任意的m個(gè)變?cè)獂i1，xi2， …，xim統(tǒng)計(jì)獨(dú)立，即對(duì)任意a1，a2，…，am和a，均有：

則稱f是m階相關(guān)免疫函數(shù)。

定義2平衡的m階相關(guān)免疫函數(shù)稱為m-彈性函數(shù)。

定義3f的Walsh譜為

這里，ωx=ω1x1+ω2x2+…+ωnxn。

由文獻(xiàn)［6］得以下定理。

定理1布爾函數(shù)f(x1，x2，…，xn)是m-彈性函數(shù)當(dāng)且僅當(dāng)對(duì)任何a∈F2n，0≤wt(a)≤m，均有F(a)=0。

由文獻(xiàn)［1］得以下定理。

定理2設(shè)布爾函數(shù)f(x1，x2，…，xn)是m-彈性函數(shù)，這里 ，n≥3并 且m≤n-3，則F(ω)≡0(mod2m+2)對(duì)任何ω∈{0 ，1}n成立。

由文獻(xiàn)［2］知道有下列定理。

定理3給定布爾函數(shù)f(x1，x2，…，xn)，若f是m-彈性函數(shù)（1≤m≤n-2），則degf+m≤n-1；若f是m-階相關(guān)免疫函數(shù)（1≤m≤n-1），則degf+m≤n。

由文獻(xiàn)［7］和文獻(xiàn)［8］知道有下列定理。

由Parseval關(guān)系有下列定理。

由文獻(xiàn)［4］可得下列定理。

定理6設(shè)f是0-彈性函數(shù)（即平衡函數(shù)），則

由文獻(xiàn)［5］可得下列定理。

定理7設(shè)f(x1，x2，…，xn)是一個(gè)m-彈性函數(shù)，則

3 主要結(jié)果

這里給出并證明主要結(jié)果。

定理8設(shè)f(x1，x2，…，xn)是一個(gè)m-彈性函數(shù)，n大于或等于3且0≤m≤n-3，則

結(jié)合定理6，定理7和定理8有以下定理。

定理 9設(shè)f(x1，x2，…，xn)是一個(gè)m-彈性函數(shù)，n大于或等于3且0≤m≤n-3，則

還可以將定理9細(xì)化。

所以此時(shí)有，σf≥2n+2m+4。因此，此下界比原來給出的下界要緊一些。

3）如果f是n-3-彈性函數(shù)，則由定理2，F(xiàn)(ω)≡0(mod2n-1)對(duì)任何ω∈{0 ，1}n成立。由定理5，要么有4個(gè)ω滿足|F(ω)|=2n-1，其余ω滿足F(ω)=0；要么有1個(gè)ω滿足|F(ω)|=2n，其余ω滿足F(ω)=0 。由定理4，要么σf=23n-2，要 么σf=23n。

當(dāng)m大于或等于n-2時(shí)，平方和指標(biāo)是確定的，見下列情況。

4）當(dāng)m等于n-2，n-1時(shí)，由定理3可知，f一定是仿射函數(shù)，因此一定有σf=23n。

5）考察3≤n≤6的情形。

（1）n=3；如果f是0-彈性函數(shù)且非仿射函數(shù)，由3）知σf=23n-2=27。如果f是0-彈性函數(shù)且是仿射函數(shù)。則σf=23n=29。如果f是1-彈性函數(shù)或2-彈性函數(shù)，由4）知，σf=23n=29。

（2）n=4；如果f是 0-彈性函數(shù)，由 1）知σf≥22n+2n+3=28+27=384。列舉所有4元平衡函數(shù)f，發(fā)現(xiàn)σf≥640。因此用這個(gè)下界。如果f是1-彈性函數(shù)且非仿射函數(shù)，由3）知σf=23n-2=210。如果f是1-彈性函數(shù)且為仿射函數(shù)，則σf=23n=212，如果f是2-彈性函數(shù)或3-彈性函數(shù)，由4）知，σf=23n=212。

（3）n=5；如果f是 0-彈性函數(shù)，由1）知道，σf≥22n+2n+3=210+28。如果f是1-彈性函數(shù)，因?yàn)?11=25+2+4＞210+28＞210+25+log26，所以，σf≥211。如果f是2-彈性函數(shù)且非仿射函數(shù)，由3）知σf=23n-2=213，如果f是2-彈性函數(shù)且為仿射函數(shù)，則σf=23n=215。如果f是3-彈性函數(shù)或4-彈性函數(shù)，由4）知，σf=23n=215。

（4）n=6；如果f是 0-彈性函數(shù)，由1）知道，σf≥22n+2n+3=212+29。如果f是1-彈性函數(shù)，因?yàn)?12+29＞212=26+2+4，212+29＞212+26+log27，因此，這個(gè)時(shí)候，σf≥22n+2n+3=212+29。如果f是2-彈性函數(shù)，因?yàn)椋?6+4+4＞212+29，26+4+4＞212+26+log222，所以這個(gè)時(shí)候，σf≥214。如果f是3-彈性函數(shù)且非仿射函數(shù)，由3）知σf=23n-2=216，如果f是3-彈性函數(shù)且為仿射函數(shù)，由3）知σf=23n=218。如果f是4-彈性函數(shù)或5-彈性函數(shù)，由4）知，σf=23n=218。

上面的 1）、2）、3）、4）、5）包含了n≥3 ，0≤m≤n-1所有情況下n變?cè)猰-彈性函數(shù)的平方和指標(biāo)的下界。

4 結(jié)語(yǔ)

布爾函數(shù)的代數(shù)免疫性質(zhì)目前已有大量文獻(xiàn)研究［9～12］。關(guān)于函數(shù)全局雪崩特征有兩個(gè)指標(biāo)，即平方和指標(biāo)與絕對(duì)指標(biāo)。這里，僅僅研究了彈性函數(shù)的平方和指標(biāo)。提出彈性函數(shù)平方和指標(biāo)一個(gè)新的下界，該下界可以與以前給出的下界結(jié)合起來使用。由這些下界發(fā)現(xiàn)：彈性函數(shù)的階m越大，則彈性函數(shù)的平方和指標(biāo)越大。但是，m很小時(shí)又要受到分別征服攻擊。因此，應(yīng)該選擇適當(dāng)大小的m，使得彈性函數(shù)的階m較大，并且同時(shí)使得平方和指標(biāo)較小。以后還應(yīng)研究彈性函數(shù)的絕對(duì)指標(biāo)［13～15］。可以預(yù)計(jì)，彈性函數(shù)的絕對(duì)指標(biāo)并沒有一個(gè)單一的下界。即對(duì)不同的彈性階，有不同的下界（由多個(gè)公式表達(dá)）。