# polynomial evaluation in GF(2) and common subexpression elimination

## "rng" <panneton@hotmail.com>21 Jun 2005 13:57:10 -0400

From comp.compilers

Related articles
polynomial evaluation in GF(2) and common subexpression elimination panneton@hotmail.com (rng) (2005-06-21)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio drizzle76@gmail.com (drizzle) (2005-06-23)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio emailamit@gmail.com (Amit Gupta) (2005-06-24)
Re: polynomial evaluation in GF(2) and common subexpression eliminatio cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-26)
| List of all articles for this month |

 From: "rng" Newsgroups: comp.compilers Date: 21 Jun 2005 13:57:10 -0400 Organization: http://groups.google.com Keywords: arithmetic, optimize, question Posted-Date: 21 Jun 2005 13:57:10 EDT

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).

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)?