FPGA Central

Hi there,

It would be great if someone could help me, or point out where I could
get some information on the following problem. I have the roots of a
polynomial (in a Galois Field), and want to evaluate the polynomial at
certain values. How can I effectively (using the least number of
operations) determine the polynomial. Someone suggested that I should
use FFT techniques. I suppose I have to use the inverse FFT, but I
don't know how to do it in a Galois Field.

After the polynomial is determined, I will use Horner's rule to
evaluate the polynomial.

Your time, effort and suggestions will be greatly appreciated
Jaco Versfeld

[email protected] asked:
>. I have the roots of a
> polynomial (in a Galois Field), and want to evaluate the polynomial at
> certain values. How can I effectively (using the least number of
> operations) determine the polynomial.
>...........
>
> After the polynomial is determined, I will use Horner's rule to
> evaluate the polynomial.


Knowing the roots of a polynomial, one cannot determine the
coefficients of the polynomial completely because f(x) and
af(x) have the same roots. Put another way, a polynomial of
degree n has n+1 coefficients while knowledge of the roots
gives only n equations from which to determine the coefficients.
Thus, something more is needed, e.g. a requirement that the
highest-degree term have coefficient 1. In what follows, I
assume that this additional requirement is imposed.

If all that is needed is to evaluate the polynomial at certain
values, say at x = a, b, c, etc., then it is *not* necessary to
find the coefficients first. If r1, r2, ..., rn are the roots,
then f(x) = (x - r1)(x - r2) ... (x- rn) and

f(a) = (a - r1)(a - r2)..... (a - rn)
f(b) = (b - r1)(b - r2) .... (b - rn)
etc

where each computation requires n additions (actually
subtractions) and n multiplications, the same as with Horner's
rule. (Hint: DO NOT multiply out the expressions and then
start using Horner's rule on x^n + ..! Instead, calculate
(a - r1) and store in an accumulator. Then compute (a - r2)
and mutiply the accumulator contents by this quantity,
storing the result in the accumulator, etc.) FFT methods
would be useful if it is needed to evaluate f(x) at all (or most
of) the n-th roots of unity since the amount of computation
can be reduced from O(n^2) to O(n log n). For just a few
evaluations, the direct method described above is far better.

Hope this helps.

Thank you very much.

Kind Regards,
Jaco Versfeld