Boolean Functions: Difference between revisions
No edit summary |
No edit summary |
||
Line 56: | Line 56: | ||
We identify the vector space with the finite field and we consider <i>f</i> an <i>n</i>-variable Boolean function of even weight (hence of algebraic degree at most <i>n</i>-1). | We identify the vector space with the finite field and we consider <i>f</i> an <i>n</i>-variable Boolean function of even weight (hence of algebraic degree at most <i>n</i>-1). | ||
The map admits a uinque representation as a univariate polynomial of the form | The map admits a uinque representation as a univariate polynomial of the form | ||
<math> f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}} | <center><math> f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n}, | ||
</math></center> | |||
with Γ<sub><i>n</i></sub> set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2<sup><i>n</i></sup>-1), <i>o(j)</i> size of the cyclotomic coset containing <i>j</i>, <i>A<sub>j</sub> ∈ 𝔽<sub>2<sup><i>o(j)</i></sup></sub>, Tr<sub>𝔽<sub>2<sup><i>o(j)</i></sup>/𝔽<sub>2</sub></sub></sub> trace function from 𝔽<sub>2<sup><i>o(j)</i></sup> to 𝔽<sub>2</sub>. | |||
Such representation is also called the univariate representation . | Such representation is also called the univariate representation . | ||
<i>f</i> can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n} | <i>f</i> can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math> where <I>P</i> is a polynomial over the finite field F<sub>2<sup>n</sup></sub> but such representation is not unique, unless <i>o(j)=n</i> for every <i>j</i> such that <i>A<sub>j</sub></i>≠0. |
Revision as of 14:27, 26 September 2019
Introduction
Let [math]\displaystyle{ \mathbb{F}_2^n }[/math] be the vector space of dimension n over the finite field with two elements. The vector space can also be endowed with the structure of the field, the finite field with [math]\displaystyle{ 2^n \mbox{ elements, }\mathbb{F}_{2^n} }[/math]. A function [math]\displaystyle{ f : \mathbb{F}_2^n\rightarrow\mathbb{F} }[/math] is called a Boolean function in dimenstion n (or n-variable Boolean function).
Given [math]\displaystyle{ x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n }[/math], the support of x is the set [math]\displaystyle{ supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \} }[/math]. The Hamming weight of x is the size of its support ([math]\displaystyle{ w_H(x)=|supp_x| }[/math]). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\ne0 \} }[/math]. The Hamming distance of two functions f,g is the size of the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g)) }[/math].
Representation of a Boolean function
There exist different ways to represent a Boolean function. A simple, but often not efficient, one is by its truth-table. For example consider the following truth-table for a 3-variable Boolean function f.
x | f(x) | ||
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Algebraic normal form
An n-variable Boolean function can be represented by a multivariate polynomial over [math]\displaystyle{ \mathbb{F} }[/math] of the form
Such representation is unique and it is the algebraic normal form of f (shortly ANF).
The degree of the ANF is called the algebraic degree of the function, [math]\displaystyle{ d^0f=\max \{ |I| : a_I\ne0 \} }[/math].
Trace representation
We identify the vector space with the finite field and we consider f an n-variable Boolean function of even weight (hence of algebraic degree at most n-1). The map admits a uinque representation as a univariate polynomial of the form
with Γn set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2n-1), o(j) size of the cyclotomic coset containing j, Aj ∈ 𝔽2o(j), Tr𝔽2o(j)/𝔽2 trace function from 𝔽2o(j) to 𝔽2.
Such representation is also called the univariate representation .
f can also be simply presented in the form [math]\displaystyle{ \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x)) }[/math] where P is a polynomial over the finite field F2n but such representation is not unique, unless o(j)=n for every j such that Aj≠0.