FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Constructing a (GF(2^m)) polynomial from its roots using FFT techniques?
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
Author Message
jaco.versfeld@gmail.com
science forum beginner


Joined: 21 Sep 2005
Posts: 11

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

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

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

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

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

Thank you very much.

Kind Regards,
Jaco Versfeld
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [3 Posts] View previous topic :: View next topic
The time now is Thu Nov 15, 2018 7:11 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Entire functions, polynomial bounds david petry Math 2 Thu Jul 20, 2006 11:09 pm
No new posts inverting a cubic polynomial as a series pluton Math 6 Tue Jul 18, 2006 4:54 am
No new posts Polynomial solving jacob navia num-analysis 4 Sun Jul 16, 2006 6:12 pm
No new posts Solving a polynomial jacob navia Symbolic 6 Sun Jul 16, 2006 5:51 pm
No new posts Eliminating multiple roots in mathematica's "Solve" function double d Symbolic 4 Sat Jul 15, 2006 11:49 am

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
[ Time: 0.0133s ][ Queries: 16 (0.0024s) ][ GZIP on - Debug on ]