Hello
I need to figure out 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 = 2
or
a * (inverse b) = x^2 * (inverse b) = 2
a * (inverse b) = x^2 * 1/x = 2
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! Especially, if someone can show me a step by step example.
Thank you very much for reading.
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.
I need to figure out 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 = 2
or
a * (inverse b) = x^2 * (inverse b) = 2
a * (inverse b) = x^2 * 1/x = 2
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! Especially, if someone can show me a step by step example.
Thank you very much for reading.
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.
