Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.