Finding the Inverse of a Polynomial in Zp[x]: Prime Algorithm

[Icebreaker]

Is there an algorithm for finding the inverse of a polynomial in Zp[x] where p is a prime?

 

[AKG]

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 xⁿ 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 x⁰ 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 x⁰ 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.

 

[Icebreaker]

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

 

[AKG]

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 Z_p[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 a_q. It's inverse would be some polynomial r(x) of degree deg(r) with leading coefficient a_r. The product q(x)r(x) should be 1, so the coefficient of x^{deg(q)+deg(r)} ought to be 0, but it will be a_qa_r 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.

 

[Icebreaker]

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.

 

[SN1987a]

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.

 

[Icebreaker]

How odd that I've tried every element and still haven't found an inverse. Time for mathematica.

 

[AKG]

Finding the inverse of ax² + bx + c:

(ax²+bx+c)(dx²+ex+f)
= adx⁴ + (ae+bd)x³ + (af+eb+cd)x² + (bf+ec)x + cf
= [adx⁴ + (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 Z₂:

(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?

 

[AKG]

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

 

[AKG]

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?

 

[Icebreaker]

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.

 

[Hurkyl]

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)!

 

[AKG]

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?

 

[Hurkyl]

It sure is!