Converting truth table to algebraic normal form Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?


I have seen that Sage has one implementation (official documentation):

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("12fe342a")
sage: B.algebraic_normal_form()
x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x3*x4 + x0*x1*x3 + x0*x1*x4 + x0*x2*x3*x4 + x0*x2*x4 + x0*x3*x4 + x0*x3 + x0 + x1*x2*x4 + x1*x3 + x1*x4 + x2*x3*x4 + x2*x3 + x2*x4


But, nowhere I could find the algorithm.

It would be helpful if someone kindly explains with a suitable example.

UPDATE The answer can be found here. It is copied below.
The sage source code implies that algebraic normal form is the same as the Fourier expansion of the function (over the group $\mathbb{Z}_2^n$, where $n$ is the number of input bits). You can compute the Fourier transform using the well-known FFT algorithm(s).