LAT de casete, suma de coloms și rânduri

să avem sbox s: Vn -> Vn.

Dacă facem un tabel LAT pentru s, fixăm orice rând și obținem o sumă pe coloane, acea sumă ar fi $+-2^{n-1}$.

Și invers, dacă fixăm orice coloană și obținem o sumă pe rânduri, acea sumă ar fi $+-2^{n-1}$ de asemenea. De ce este așa?

Elementul din rândul „a”, coloana „b” a LAT este $#{<a, x>=<b,s(x)>} - 2^{n-1}$. Unde <,> este un produs scalar.

Suma este o sumă de numere întregi care sunt într-o coloană a matricei/un rând de matrice.

În primul rând, un rând/coloană de LAT corespunde unei funcții componente a casetei S/inversul acesteia (o combinație liniară de ieșiri). Deci, să derivăm valoarea sumei tuturor coeficienților Walsh ai oricărei funcții booleene.

Voi folosi această definiție a transformării Walsh. Rezultatele pentru alții pot fi adaptate cu ușurință.

$$W_f(a) = \sum_{x\in F_n} (-1)^{\langle a, x\rangle + f(x)},$$ $$\sum_{a \in F_n}W_f(a) = \sum_{a \in F_n}\sum_{x\in F_n} (-1)^{\langle a, x\rangle + f(x)} = \sum_{x\in F_n}\big((-1)^{f(x)}\sum_{a \in F_n}(-1)^{\langle a, x\rangle}\big).$ $ Suma interioară este egală cu zero oricând $x\ne 0$ (funcțiile liniare sunt echilibrate) și este egal cu $2^n$ când $x=0$. Primim $$\sum_{a \in F_n}W_f(a) = 2^n\cdot (-1)^{f(0)}.$$

Acest lucru îl puteți observa de ex. pe SageMath's BooleanFunction.walsh_hadamard_transform.