# Inverses in Truncated Polynomial Rings

I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it. Read this, please:

The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ combined with the modular arithmetic described in Section 1. These are combined by reducing the coefficients of a polynomial a modulo an integer $q$. Thus the expression $$a \pmod q$$ means to reduce the coefficients of $a$ modulo $q$. That is, divide each coefficient by $q$ and take the remainder. Similarly, the relation $$a \equiv b \pmod q$$ means that every coefficient of the difference $a-b$ is a multiple of $q$.

This is taken from NTRU tutorial and that's quite understandable. But. Take a glance at the next excerpt from the same tutorial:

The inverse modulo $q$ of a polynomial $a$ is a polynomial $A$ with the property that $$a * A \equiv 1 \pmod q.$$

Not every polynomial has an inverse modulo $q$, but it is easy to determine if $a$ has an inverse, and to compute the inverse if it exists. A fast algorithm for computing the inverse is described in NTRU Technical Note 014, and a theoretical discussion of inverses in truncated polynomial rings is given in NTRU Technical Note 009. These notes may be downloaded from the Technical Center.

Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The inverse of $a$ modulo 11 is $$A=-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6,$$ since $$(3+2X^2-3X^4+X^6)*(-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6) \\ = -10+22X+22X^3-22X^6 \equiv 1 \pmod{11}."$$

I do not understand how $-10+22X+22X^3-22X^6$ may be 1 (modulo 11). Why???????

The first excerpt adduced says that each coefficient of the polynomial minus 1 must be a quotient of 11. But it's not. -10? That's not a problem. $-10 - 1 = -11$. $-11 \bmod 11$ is 0, yes, it works, I agree. But how can it work with 22? $22 - 1 = 21$. $21 \bmod 11 = 10$, not 0. also it doesn't work with $- 22$. $-22 - 1 = -23$. $-23 \bmod 11 = -1$. Can anyone, please, explain me this example?

• 22x = 0 mod 11 because 22 is a multiple of 11, the same for 22x³ and -22x⁶, then you have only -10 which is congruent to 1 mod 11. – Vicfred Dec 26 '11 at 22:36
• Exactly! That is the problem! 22x = 0 mod 11. I understand it. So how -10+22X+22X3-22X6 may be 1 (modulo 11) if 22 = 0 mod 11? This is what i can not understand – Andrey Chernukha Dec 27 '11 at 10:08
• because -10 = 1 (mod 11) – Vicfred Dec 27 '11 at 21:19

$$(-10+22x+22x^3-22x^6) - 1 = -11+22x+22x^3-22x^6 \equiv 0 \mod 11.$$

When substracting a constant from a polynomial, you do not subtract it from every term, only from the constant term.

If you need a refresher, see addition and subtraction of polynomials.

"how $-10+22X+22X^3-22X^6$ may be 1 (modulo 11) if 22 = 0 mod 11?"

Because when you reduce this mod 11 you get

$$1 + 0 X + 0 X^3 + 0 X^6 = 1.$$

You seem to think that saying a polynomial is 1 mod 11 means that all its terms are 1 mod 11. What it actually means is that the constant term is 1 mod 11, and all the other terms are 0.