reduces the coefficients of a modulo 3 on NTRU

i'm still don't understand about 'reduces the coefficients of a modulo 3' on NTRU tutorial

$a = f*e = 3 - 7X - 10X^2 - 11X^3 + 10X^4 + 7X^5 + 6X^6 + 7X^7 + 5X^8 - 3X^9 -7X^{10} \pmod{32}.$ Note that when Bob reduces the coefficients of $f*e \bmod{32}$, he chooses values lying between -15 and 16, not between 0 and 31. It is very important that he choose the coefficients in this way.

Next Bob reduces the coefficients of a modulo 3 to get $b = a = - X - X^2 + X^3 + X^4 + X^5 + X^7 - X^8 - X^{10} \pmod{3}$.

how can you get polynomial $a \bmod{3}$ is : $- X - X^2 + X^3 + X^4 + X^5 + X^7 - X^8 - X^{10}$? what i know on 'polynomial $a \bmod{3}$' means every coefficient mod 3, so coefficient on $-X^8$ should be $2$ ($2X^8$) not $-1$ ($-X^8$), because $5 \bmod 3 = 2$?

-

1 Answer

Reducing mod 3 means indeed reducing each coefficient mod 3, and again we choose the representatives symmetrically around 0, so each coefficient becomes -1,0 or 1 (instead of, which is also possible, 0,1, and 2, or some other choice).

$-7X$ becomes $-X$ because $-7 \equiv -1 \mod 3$. The starting constant 3, becomes 0, and disappears, $-10X^2$ becomes $-X^2$ (adding 9), $-11X^3$ becomes $X^3$, as $-11 \equiv 1 \mod 3$ (add 12 to the left) etc. etc.

Your final example $5X^8$ could become $2X^5$, but also (subtracting 3 again, to get a representative from $\{-1,0,1\}$) the actually used $-X^8 = (-1)X^8$.

So mod 3 is actually a bit more restrictive: replace each coefficient by its unique equivalent value in among -1,0 and 1, not just any representative that would be equivalent to it. As your quote says "It is very important that he choose the coefficients in this way" (not only for 32, also for 3).

-
ok good, i get it now, so this is the same as you find 'small polynomial over modulo p' like happens on the NTRUencryption process? or they are different? –  Sunia Raharja Mar 23 '13 at 4:08