對稱布爾函數(shù)代數(shù)免役的研究.pdf

1、為了抵制代數(shù)攻擊，布爾函數(shù)應(yīng)當(dāng)具有較高的代數(shù)免疫。在布爾函數(shù)中，對稱布爾函數(shù)又是其中重要的一類。一個(gè)n元布爾函數(shù)可以轉(zhuǎn)化為一個(gè)長為2<'n>的向量，而對于對稱布爾函數(shù)，重量相等的向量，其函數(shù)值相等。任意一個(gè)n維向量x其重量滿足：0≤wt(x)≤n。這樣，就可以把一個(gè)n元對稱布爾函數(shù)轉(zhuǎn)化為一個(gè)n+1維向量v<,f>=(v<,f>(0)，v<,f>(1)…v<,f>(n))，其中V<,f>(i)表示重量為i的函數(shù)值，0≤i≤n，此向量v<,

2、f>稱為對稱函數(shù)f的向量值(VV)，極大地減少了對存儲(chǔ)空間的需求，并且在軟件應(yīng)用中發(fā)揮著重要作用。而每個(gè)對稱函數(shù)都可寫成齊次對稱函數(shù)σ<,i>(0≤i≤n)為基的線性組合其中向量λ<,f>=(λ<,f>，(0)，λ<,f>(1)…λ<,f>(n))稱為簡化的ANF向量。本文主要的工作都是基于V<,f>(i)進(jìn)行構(gòu)造。 第一章介紹了布爾函數(shù)的基本知識(shí)，對其中的一些性質(zhì)進(jìn)行了簡單的推廣。第二章從代數(shù)免疫的定義出發(fā)，通過零化子的性質(zhì)，