# 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.