# Difference between revisions of "Boolean Functions"

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 15:27, 26 September 2019

## Contents

# 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 2^{n}-1), *o(j)* size of the cyclotomic coset containing *j*, *A _{j} ∈ π½_{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 F_{2n} but such representation is not unique, unless *o(j)=n* for every *j* such that *A _{j}*≠0.