Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a doubt about the modular inverse polynomial degree.

Let $p(X)$ be a polynomial in the ring $F[X]$ with $\deg(p)=\delta$, where $F$ is a finite field with characteristic 2. If $\gcd(p(X),q(X)) = 1$, what is the degree of the inverse polynomial of $p(X)$ modulo $q(X)$?

Thanks for your replies.

share|improve this question
2  
Since $F[X]$ is a Euclidean domain, the degree of $f^{-1} \bmod q < \deg(q).$ Also, the inverse of $p$ is $u\bmod q$ for the Bézout coefficients $u, v$ in $pu + qv = 1.$ –  user2468 Jul 19 '12 at 18:34
2  
And more than @J.D. says above, can not be determined. You can’t expect to say anything reasonable about the degree of the reciprocal other than that it’s generically $1$ less than the degree of $q$. –  Lubin Jul 19 '12 at 18:48
1  
Just to complete the above comments, note that for any positive integers $m,n$, the inverse of $X^n$ modulo $X^{m+n}-1$ is $X^m$. –  N. S. Jul 19 '12 at 19:03

1 Answer 1

up vote 1 down vote accepted

If you take a Bezout relation in $F[X]$ $$u(X)p(X)+v(X)q(X)=1$$ the inverse of $p(X)$ modulo $q(X)$ is $u(X)$. Now i don't really understand what you mean by the "degree" of the inverse, but if you want the degree of an inverse which is of degree lesser than $\deg(q)$, you should just work out this Bezout relation and see that it gives $\deg(u)+\deg(p)=\deg(v)+\deg(q)$ as long as $q$ is not trivial.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.