polynomial evaluation in GF(2) and common subexpression elimination

Hi,


I have a polynomial f(z) with coefficients in GF(2) that I want to
evaluate at a point z, (an example is f(z) = z^256 + z^255 + z^2 + z
+1). Typically, the polynomial has hundreds of non-zero coefficients.


What I am looking for is a general algorithm that will reduce the
number of additions (i.e. xors). For exemple, for f(z) = z^256 +z^255
+z^2+z +1, I
can write
g(z) = z + 1
f(z) = z^255 h(z) + z^2 + h(z).
which is done with 3 additions instead of 4.


In my problem, the z is in fact a linear operator "A" that is applied
to a bit vector and that returns a bit vector of the same size. So,
A^n correspond to applying the operator n times. I want to compute
f(A)v, where v is a bit vector. The linear operator is very cheap to
compute, but the additions (i.e. xors) are very expensive since the bit
vectors are typically of size 20000 bits.


I have read that I can do this with a method called "common
subexpression elimination", but I cannot find a reference that clearly
explains it.


Do you have a good reference for "common subexpression elimination"
(applied to polynomial evaluation preferably)?


Do you have any advice?


Thank you.
Francois.

Return to the comp.compilers page.
Search the comp.compilers archives again.