I am trying to understand the modular inverse of a polynomial. Let $A , Q$ be polynomials; what is the polynomial $B$ such that $A B = 1 \pmod Q$?
I tried searching articles from Finding inverse of polynomial in a field and http://people.mpi-inf.mpg.de/~csaha/lectures/lec5.pdf but could not find enough.
Any help is appreciated, thank you.
You need to find $U$ and $V$ polynomial over your field such that :
$$A(x)U(x)+Q(x)V(x)=1 $$
This is the Bezout Identity for polynomials over $F[x]$ (here $F$ is the base field you are implicitely working with).
Such $U$ and $V$ exists if and only if $gcd(A,Q)=1$ if and only if $A$ is invertible modulo $Q$. Now take $A$ invertible mod $Q$ by what is written before there exists $U$ and $V$ such that :
$$A(x)U(x)+Q(x)V(x)=1 $$
Hence if you look at this equation mod $Q$ it gives $AU=1$ mod $Q$. So the inverse you are looking for is the polynomial $U$ in the Bezout identity.
Last question "how to compute a Bezout identity"? It is just making an extended Eculidean algorithm... see https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor