Search   Memberlist   Usergroups
 Page 1 of 1 [3 Posts]
Author Message
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
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?

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [3 Posts]
 The time now is Sat Nov 17, 2018 11:11 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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