A-6.2 Polynomial Decomposition

This time, suppose we have a polynomial $f$ in the polynomial ring ${\mathbb{Z}}_q[x]∕(x^n+1)$. Therefore, each coefficient $c_i$ of $f$ is an integer modulo $q$. Polynomial decomposition expresses $f$ as a sum of multiple polynomials in base $\beta$ and level $\ell$ as follows:

A-6.2.1 Example

Suppose we have the following polynomial in the polynomial ring ${\mathbb{Z}}_{16}[x]∕(x^4+1)$:

$f=6x^3+3x^2+14x+7\in {\mathbb{Z}}_{16}[x]∕(x^4+1)$

Suppose we want to decompose the above polynomial with base $\beta =4$ and level $\ell =2$. Then, each degree’s coefficient of the polynomial $f$ is decomposed as follows:

${𝐱}^3$: $6=1\cdot {\displaystyle \frac{16}{4^1}}+2\cdot {\displaystyle \frac{16}{4^2}}$

${𝐱}^2$: $3=0\cdot {\displaystyle \frac{16}{4^1}}+3\cdot {\displaystyle \frac{16}{4^2}}$

${𝐱}^1$: $14=3\cdot {\displaystyle \frac{16}{4^1}}+2\cdot {\displaystyle \frac{16}{4^2}}$

${𝐱}^0$: $7=1\cdot {\displaystyle \frac{16}{4^1}}+3\cdot {\displaystyle \frac{16}{4^2}}$

The decomposed polynomial is as follows:

$f=6x^3+3x^2+14x+7=(1x^3+0x^2+3x+1)\cdot {\displaystyle \frac{16}{4^1}}+(2x^3+3x^2+2x+3)\cdot {\displaystyle \frac{16}{4^2}}$

${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{4,2}(6x^3+3x^2+14x+7)=(1x^3+0x^2+3x+1,2x^3+3x^2+2x+3)$

A-6.2.2 Discussion

Note that after decomposition, the original coefficients of the polynomial have been reduced to smaller numbers. This characteristic is importantly used in the multiplication of polynomials in FHE ciphertexts to reduce the growth rate of the noise. Normally, the polynomial coefficients of ciphertexts are large because they are uniformly random numbers. Reducing such large constants is important for reducing the noise growth during homomorphic multiplication. We will discuss this in more detail in §D-1.6.