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?
