# Fast algorithms for addition and multiplication of Zhegalkin polynomials

Hello to all,

I'm interested in fast algorithms for addition and multiplication of Zhegalkin polynomials. For example, let

$f_1(x_1, x_2, x_3) = 1+x_1+x_2x_3$

$f_2(x_1, x_2, x_3) = x_1+x_3$

I'd like to have a fast algorithm to find the sum

$f_3(x_1, x_2, x_3) = f_1(x_1, x_2, x_3)+f_2(x_1, x_2, x_3)=1+x_3+x_2x_3$

Google gives nothing, so I would be grateful for any useful links to any theoretical researches and/or realizations (with any program language).

-
This question does not really make sense: What do you mean by "fast"? How do you represent your polynomials (by a list of monomials? Straight line programs? values at a set of points?) –  Igor Rivin Dec 29 '11 at 10:45

If you are interested in parallel computing, the article

V. D. Malyugin, V. V. Sokolov, “Intensive logic computations”, Avtomat. i Telemekh., 1993, no. 4, 160–167 (in Russian) [English version: Automation and Remote Control, 1993, 54:4, 672–678]

may be useful.

-
"Fast" means "faster that the obvious direct calculation". For example, FFT allows us to multiply two polynomials $F(x)P(x)$ over $R$ faster that the obvious direct calculation. I need something like this for Zhegalkin polynomials.