1
$\begingroup$

I'm reading this introductory blog on the Fan-Vercauteren scheme and there are a few things I don't understand about polynomial moduli. The author uses practical examples:

Because we are considering remainders with respect to $x^{16}+1$, we only have to consider polynomials with powers from $x^0$ to $x^{15}$. Any larger powers will be reduced by division by the polynomial modulus. This can also be understood by considering that $x^{16}\equiv −1(\mathrm{mod} \ x^{16}+1)$, meaning that $x^{16}$ can be replaced by -1 to reduce the larger powers of x into the range 0 to 15.

I don't understand the third sentence at all, $x^{16} \equiv -1$?

Further down the tutorial, there is a practical example of polynomial multiplication followed by a division by polynomial modulus:

When we multiply two powers of x, say $2x^{14}$ and $x^4$, we add their exponents - making $2x^{18}$. One might assume that finding the remainder of this polynomial with respect to the polynomial modulus might involve just rotating the exponent back through 0 at $x^{16}$, to give $2x^{2}$, like it does for the integer coefficients shown above. This would be the case if the polynomial modulus was just $x^{16}$. However, our polynomial modulus is $x^{16}+1$ - as mentioned above, the extra plus one factor introduces a sign change which helps further scramble the result of the multiplication.

How does this extra plus one factor introduce a sign change?

and finally:

...multiplication of a term $2x^{14}$ by $x^4$ modulo $x^{16}+1$ takes this term (represented by the red dot above), rotates it forward 4 powers around the torus, and then reflects the value across the 0 point, making $22x^2$ (or $−2x^2$ if we consider numbers from -12 to 11 rather than 0 to 23).

$2x^{18}$ modulo $x^{16}+1 = 22x^2$, how?

$\endgroup$
  • $\begingroup$ Do you know how to do polynomial division? $\endgroup$ – DRF Nov 28 '18 at 14:36
2
$\begingroup$

You have to pay attention to the fact that two moduli are used: a polynomial modulus $x^n + 1$ and an integer modulus $t$ (in that example, $n = 16$ and $t = 24$).

In practice, it means that not only the degree is limited but also the coefficients: they always lie in $\mathbb{Z}_t$, which is traditionally represented as the set $[0, t-1] \cap \mathbb{Z}$, but in lattice-related texts, it is usually represented as $[-t/2, t/2) \cap \mathbb{Z}$.

So, for the first point, it is easy if you think that for any polynomial $p(x)$, reducing it modulo itself results in a zero, i.e., $p(x) \equiv 0 \pmod{ p(x)}$, because the division $p(x) / p(x)$ is $1$ with remainder $0$. Hence, taking $p(x) = x^n+1$ gives us

$$x^n+1 = 0 \pmod{x^n+1} \Rightarrow x^n = -1 \pmod{x^n+1}.$$

Now, if you use the properties of modular multiplication, you will see that when you reduce a polynomial modulo $x^n +1$, you will actually replace the powers $x^n$ by $-1$, $x^{n+1}$ by $-x$, $x^{n+2}$ by $-x^2$, etc.

Thus, for instance, $2x^{14} \cdot x^4 = 2x^{18} = 2x^2 \cdot x^{16}$. But since $x^{16} = -1$ because of the modular reduction, we have

$$2x^{14} \cdot x^4 = -2x^2 \pmod{x^{16}+1}.$$

Until this point, only the polynomial reduction was done, but we also need to compute each coefficient modulo $t = 24$. Since $-2 = 22 \mod 24$ we get

$$2x^{14} \cdot x^4 = 22x^2 \pmod{x^{16}+1, t}.$$

Notice that if we use the representation of $\mathbb{Z}_t$ that includes negative numbers, then $-2$ equals itself modulo $t$ and the result is still $-2x^2$, as it is said in the last parenthesis of your question.

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