# computing inverses in truncated polynomial rings manually for NTRU encryption [duplicate]

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?

• I don't get your "not pseudo-code". To do it manually, you should execute the pseudo-code manually. – CodesInChaos Mar 11 '13 at 10:13
• I want to know all step of the process, so i can solve it with handwriting, if its posible – Sunia Raharja Mar 11 '13 at 10:22
• 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. – mikeazo Mar 11 '13 at 13:02
• 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 – mikeazo Mar 11 '13 at 13:11
• 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. – Henno Brandsma Mar 11 '13 at 21:39