I am working with polynomials in the ring $\mathbb{Z}[X]/(X^n-1)$, so only polynomials with degree at most $n-1$ are allowed, and multiplications must be reduced modulo $X^n-1$. The thing is that I have a polynomial $f(X)$ and I want to compute its inverse modulo an integer $p$, $f_p(X)$, such that $$ f * f_p \equiv 1 \bmod p $$ How could I do that? Any known algorithm? I have heard about the extended Euclidean algorithm, but I'm not quite sure how to use it, for example, given $f(X) = -1+X+X^2-X^4+X^6+X^9-X^{10}$.
How to compute inverse polynomials modulo an integer
$\begingroup$
polynomials
ring-theory
euclidean-algorithm