4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vicfred
    Dec 26 '11 at 22:36
  • $\begingroup$ 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 $\endgroup$
    – Andrey Chernukha
    Dec 27 '11 at 10:08
  • 1
    $\begingroup$ because -10 = 1 (mod 11) $\endgroup$
    – Vicfred
    Dec 27 '11 at 21:19
4
$\begingroup$

$$(-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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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