Multiplicative inverse of a polynomial

AARRRGH

Hello

I know this is kind of a maths question, but I am trying to code the multiplicative inverse of a polynomial.

Quick explanation -

Let's say you want to divide a by b, i.e. a / b. Instead of using division, you can find the multiplicative inverse of b and multiply instead.

For example:

a = 20
b = 5

a / b = 20 / 5 = 4
or
a * (inverse b) = 20 * (inverse b) = 4
a * (inverse b) = 20 * 1/5 = 4

So as you can see, the inverse of b is simply changing 5/1 to 1/5.

This is straightforward.

Now let's have a polynomial example:

a = x^2
b = x

a / b = x^2 / x = x
or
a * (inverse b) = x^2 * (inverse b) = x
a * (inverse b) = x^2 * 1/x = x

Again, this is fairly straightforward.

But what if a and b are more complicated?

For example:

a = x^7 + x^5 + x + 1
b = x^6 + x^2 + x

a / b = x^7 + x^5 + x + 1 / x^6 + x^2 + x = 1 remainder x^5 + x^2 + x
a * (inverse b) = x^7 + x^5 + x + 1 * (inverse b) = 1 remainder x^5 + x^2 + x

How can I figure out the inverse of b?!

Any help greatly appreciated!

Thanks

PS I know the Extended Euclidean Algorithm and "Repeated Square and multiply" can be used, but I'm yet to come across an example which uses polynomials. I have no problem getting the multiplicative inverse of a natural number.

AARRRGH

Ah... found a lovely explanation: http://mathforum.org/library/drmath/view/51675.html