# Truth table to ANF conversion

It is sometimes important to be able to quickly convert a binary function, described in as a truth table, to its Algebraic Normal Form (or simply, ANF). The truth table basically lists the points where a function is 1 and when it is 0. For instance, if the function has two variables, and its truth table is `0110` or, in hexadecimal form, `0x5` then the ANF of this function is simply `x0 + x1`, where `x0` is the first variable of the function, and `x1` is the second.

When it comes to more complex functions, an automatic method for this conversion is helpful. The Sage software can do exactly that:

```sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("0123456789ABCDEF")
sage: B.algebraic_normal_form()
x0*x1*x2 + x0*x1*x3 + x0*x1*x4 + x0*x1*x5 + x0*x2
+ x0*x3 + x1*x2 + x1*x4 + x2 + 1```

Here, we used Sage to convert the function given by the truth table (in hex) `0x0123456789ABCDEF` to its ANF equivalent.

I have long searched for a method for this, but at the end it was Luk Bettale who showed me the way. Many thanks to him for this!