Author 
Message 
jaco.versfeld@gmail.com science forum beginner
Joined: 21 Sep 2005
Posts: 11

Posted: Mon Jul 10, 2006 9:10 am Post subject:
Constructing a (GF(2^m)) polynomial from its roots using FFT techniques?



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 

Back to top 


dvsarwate@gmail.com science forum beginner
Joined: 10 Jul 2006
Posts: 1

Posted: Mon Jul 10, 2006 1:44 pm Post subject:
Re: Constructing a (GF(2^m)) polynomial from its roots using FFT techniques?



jaco.versfeld@gmail.com asked:
Quote:  . 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
highestdegree 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 nth 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. 

Back to top 


jaco.versfeld@gmail.com science forum beginner
Joined: 21 Sep 2005
Posts: 11

Posted: Thu Jul 13, 2006 6:11 am Post subject:
Re: Constructing a (GF(2^m)) polynomial from its roots using FFT techniques?



Thank you very much.
Kind Regards,
Jaco Versfeld 

Back to top 


Google


Back to top 



The time now is Thu Jan 24, 2019 12:29 am  All times are GMT

