# Difference between revisions of "Boolean Functions"

m (→Trace representation) |
|||

Line 52: | Line 52: | ||

The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>. | The degree of the ANF is called the <em> algebraic degree</em> of the function, <math>d^0f=\max \{ |I| : a_I\ne0 \}</math>. | ||

+ | |||

+ | ==Trace representation== | ||

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

+ | <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}, | ||

+ | |||

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

+ | |||

+ | <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>≠0. |

## Revision as of 14:40, 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
Such representation is also called the univariate representation .

*f* can also be simply presented in the form but such representation is not unique, unless *o(j)=n* for every *j* such that *A _{j}*≠0.