|
|
| 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
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. |
|
| 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 Tue Jun 28, 2011 11:04 pm | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
