Difference between revisions of "Boolean Functions"

From Boolean Functions
Jump to: navigation, search
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)}}\setminus\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n},
+
<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 &Gamma;<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> &isin; 𝔽<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>.
 +
 
  
βˆ’
\mbox{with } \Gamma_n \mbox{ set of integers obtained by choosing one element in each cyclotomic coset of 2 } (\mod 2^n-1), o(j) \mbox{ size of the cyclotomic coset containing }j, A_j\in\mathbb{F}_{2^{o(j)}}, \mbox{Tr}_{\mathbb{F}_{2^{o(j)}}\setminus\mathbb{F}_2} \mbox{ trace function from } \mathbb{F}_{2^{o(j)}} \mbox{ to } \mathbb{F}_2.
 
βˆ’
</math>
 
 
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}\setminus\mathbb{F}_2}(P(x))\mbox{ where } P \mbox{ is a polynomial over the finite field } \mathbb{F}_{2^n}</math> 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>&ne;0.
+
<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>&ne;0.

Revision as of 15:27, 26 September 2019

Introduction

Let 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 . A function is called a Boolean function in dimenstion n (or n-variable Boolean function).

Given , the support of x is the set . The Hamming weight of x is the size of its support (). Similarly the Hamming weight of a Boolean function f is the size of its support, i.e. the set . The Hamming distance of two functions f,g is the size of the set .

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 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, .

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 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.