1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inverse of Polynomial

  1. Nov 7, 2005 #1
    Is there an algorithm for finding the inverse of a polynomial in Zp[x] where p is a prime?
     
  2. jcsd
  3. Nov 7, 2005 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Method of undetermined coefficients? Take a polynomial p(x), and for generality, express an undetermined polynomial q(x) as an infinite power series (although you know that all but finitely many of the coefficients will be 0), and you should be able to find an expression for the coefficient for xn in p(x)q(x) as some sum of terms made up of coefficients form p(x) and coefficients from q(x). You'll get that the coefficient of x0 in this product will of course be p(0)q(0), and you want this to be 1, so you can solve for the coefficient q(0). Next, you'll have some coefficient for x, and knowing the coefficients of p, and knowing q(0) (which is the coefficient of x0 in q(x)) you should be able to find another coefficient of q, since the coefficent of x in the product will have to equal 0. Continuing this process, you can determine the undetermined coefficients.
     
  4. Nov 7, 2005 #3
    This seems unlikely; I've seen this method in ODE but not in algebra. There must be something relating to the division algorithm in F[x].
     
  5. Nov 7, 2005 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    The method of undetermined coefficients is just where you have undetermined coefficients and you determine them. It is a general idea. You can apply it to ODEs, but say you have a 2x2 matrix. Say you want to find its inverse. Multiply it by some general matrix with undetermined coefficients, and you'll get a bunch of linear equations for which you can solve for the undetermined coefficients and thereby find the inverse (if your original matrix was invertible). Suppose you have a power series f(x) and you want to find a power series g(x) such that f(x)g(x) = 1. Then you would do this by undetermined coefficients, i.e. g(x) is a power series with undetermined coefficients, then you can express f(x)g(x) as a power series with coefficients in terms of those of f and those of g, giving you a bunch of equations in which you can solve the undetermined coefficients.

    Anyways, is Zp[x] even a field. I haven't studied much of this, but are you sure that elements have inverses? Suppose you have some polynomial q(x) of degree deg(q) with leading ceofficient aq. It's inverse would be some polynomial r(x) of degree deg(r) with leading coefficient ar. The product q(x)r(x) should be 1, so the coefficient of xdeg(q)+deg(r) ought to be 0, but it will be aqar which cannot be 0 if p is prime.

    If this is right, then only polynomials of degree 0 have inverses. Or am I way off? Maybe I even have the multiplication wrong. When I've studied polynomial rings, the multiplication of polynomials has been p(x)q(x), but maybe you're studying something different where multiplication is composition, i.e. p(q(x)). In this case identity would be x, not 1, and the question of finding inverses gets more complicated, I think.
     
  6. Nov 7, 2005 #5
    I'm sorry, I did not post all hypotheses; I'm in the ring Z_2[x]/(x^3+x+1). I'll try to apply your method. Every element in this ring SHOULD be invertible due to a theorem that says if F is a field and p(x) is irreducible, then F[x]/p(x) is a field.

    Every element of this ring/field is of the form ax^2+bx+c and a,b,c are either 0 or 1. I am currently brute-forcing it.
     
    Last edited by a moderator: Nov 7, 2005
  7. Nov 7, 2005 #6
    I brute-forced it too at first. In this particular case it turns out to be pretty easy: ring only has 7 elements. However, the method of undetermined coefficients works just as well, once again because this is a small ring and we don't have too many of them undetermined coefficients, so that it's not to hard to do the division algorithm.
     
  8. Nov 7, 2005 #7
    How odd that I've tried every element and still haven't found an inverse. Time for mathematica.
     
  9. Nov 7, 2005 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Finding the inverse of ax² + bx + c:

    (ax²+bx+c)(dx²+ex+f)
    = adx4 + (ae+bd)x³ + (af+eb+cd)x² + (bf+ec)x + cf
    = [adx4 + (ae+bd)x³ + (af+eb+cd)x² + (be+ec)x + cf] - adx(x³+x+1)
    = (ae+bd)x³ + (af+eb+cd-ad)x² + (be+ec-ad)x + cf
    = [(ae+bd)x³ + (af+eb+cd-ad)x² + (be+ec-ad)x + cf] - (ae+bd)(x³+x+1)
    = (af+eb+cd-ad)x² + (be+ec-ad-ae-bd)x + (cf-ae-bd)
    = 1

    So af+eb+cd-ad = 0
    be+ec-ad-ae-bd = 0
    cf-ae-bd = 1

    You have 3 equations and 3 unknowns (d, e, and f), so you should be able to solve. This is the method of undetermined coefficients.

    (c-a)d + be + af = 0
    (-a-b)d + (b+c-a)e = 0
    (-b)d + (-a)e + cf = 1

    Since the field is Z2:

    (c+a)d + (b)e + (a)f = 0
    (a+b)d + (a+b+c)e = 0
    (b)d + (a)e + (c)f = 1

    Suppose a = b = c = 1. Then:

    e + f = 0
    e = 0
    d + e + f = 1

    The second equation gives e = 0. Combining that with the first gives f = 0. Combining those with the last gives d = 1, so the inverse of x² + x + 1 is x².

    What exactly would you do with the division algorithm?
     
  10. Nov 7, 2005 #9

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Also, you should be able to see right away that the inverse of x² + 1 is x, since:

    (x² + 1)x = x³ + x = (x³ + x) - (x³ + x + 1) = -1 = 1
     
  11. Nov 7, 2005 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Actually, you know that x³ + x = 1, so maybe this is how you'd use the division algorithm? I.e. if you want to find the inverse of p(x), you'd divide x³+x by p(x) so that you'd get some q(x) such that x³+x = p(x)q(x) (and given that we have a field, you will be able to find such a q(x)) and then this q(x) would be your inverse?
     
  12. Nov 7, 2005 #11
    That's pretty much how I did it, yes. I'll keep this method of undetermined coefficients in my bag of tricks for later, though.
     
  13. Nov 7, 2005 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You could borrow tricks from modulo arithmetic (since that's essentially what this is): use GCDs to compute inverses! (The extended Euclidean algorithm, in particular)

    If f(x) and p(x) are relatively prime, then there are polynomials u and v such that:
    u(x) f(x) + v(x) p(x) = 1
    and then u(x) is an inverse of f(x) modulo p(x)!
     
  14. Nov 8, 2005 #13

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Nice. And so p(x) = x³+x+1 being irreducible is relatively prime to everything, in particular all the f(x) in our quotient field?
     
  15. Nov 8, 2005 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It sure is!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?