Can someone explain how to find inverses in truncated polynomial rings manually (i.e. on pen and paper)? As an example from the tutorial:

Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The inverse of $a \bmod 11$ is $a^{-1}=-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6$, since

$(3+2X^2-3X^4+X^6)*(-2+4^X+2X^2+4X^3-4X^4+2X^5-2X^6) \equiv -10+22X+22X^3-22X^6 \equiv 1 \mod 11$.

How to find $a^{-1} = -2+4X+2X^2+4X^3-4X^4+2X^5-2X^6$, manually, not using the pseudocode?

  • 2
    $\begingroup$ I don't get your "not pseudo-code". To do it manually, you should execute the pseudo-code manually. $\endgroup$ Commented Mar 11, 2013 at 10:13
  • $\begingroup$ I want to know all step of the process, so i can solve it with handwriting, if its posible $\endgroup$ Commented Mar 11, 2013 at 10:22
  • 3
    $\begingroup$ To be honest, there is typically a fair amount of work required to do this by hand even for such a small example. It requires long division of polynomials as you are basically doing the extended euclidean algorithm, then substituting back up until you get something of the form $p_1a+p_2b=1$ where $p_1,p_2$ are polynomials and $b=x^7-1$. Since $x^7-1\equiv 0$ in your ring, you have $p_1a=1$ so $a^{-1}=p_1$. Not sure if someone here will be willing to work everything out by hand. We'll see. Just being realistic though. $\endgroup$
    – mikeazo
    Commented Mar 11, 2013 at 13:02
  • 2
    $\begingroup$ A fairly simple algorithm (extended euclidean algorithm) tells you exactly what you need to do to solve the problem. To better understand the algorithm, start with simple integers as in this question $\endgroup$
    – mikeazo
    Commented Mar 11, 2013 at 13:11
  • 1
    $\begingroup$ Basically, using Extended Euclidean, do the inverse computation of $a$ in $\mathbb{Z}[X]$, doing the gcd with $X^7 - 1$, and reduce the coefficients modulo 11 afterwards. $\endgroup$ Commented Mar 11, 2013 at 21:39


Browse other questions tagged or ask your own question.