Bit decomposing a polynomial in BGV cryptosystem I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a vector of polynomial in $R_q^n$, in particular, how the $u_j$'s are in $R_2^n$.

Does it assume that the polynomial is in coefficient representation? Can someone please give an example for $n=1$, and $n=2$?
To understand that, we have to understand how it works for a single polynomial (which means, for $n = 1$).

First of all, think about the binary decomposition of an integer value: given $m \in \mathbb Z_q$, it is always possible to write $m = \sum_{i=0}^{\log q} b_i 2^i$, with each $b_i$ in $\{0, 1\}$.

Now, just see that if you decompose each coefficient $a_i$ of a polynomial into the binary representation $\sum_{j=0}^{\log q} b_{j,i} 2^j$ , you get $\log q$ polynomials:

$\begin{align}
p(x) &amp;= a_dx^d + a_{d-1}x^d_{d-1} + ... + a_1x + a_0\\
     &amp;= \left( \sum_{j=0}^{\log q} b_{j,d} 2^j \right)x^d + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j \right)x^{d-1} + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^j  \right)x^1 + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
    &amp;= \left( \sum_{j=0}^{\log q} b_{j,d} 2^jx^d \right) + \left( \sum_{j=0}^{\log q} b_{j,d-1} 2^j x^{d-1} \right) + ... + \left( \sum_{j=0}^{\log q} b_{j,1} 2^jx^1  \right) + \sum_{j=0}^{\log q} b_{j,0} 2^j\\
     &amp;=  \sum_{j=0}^{\log q} \left(b_{j,d} 2^j x^d + b_{j,d-1} 2^j x^{d-1} + ... + b_{j,1} 2^j x^1 + b_{j,0} 2^j \right) \\
     &amp;=  \sum_{j=0}^{\log q} \left(b_{j,d} x^d + b_{j,d-1} x^{d-1} + ... + b_{j,1} x^1 + b_{j,0} \right)  2^j \\
     &amp;=  \sum_{j=0}^{\log q} u_j(x)2^j
\end{align}$

Therefore, what this BitDecomp function does when it receives a single polynomial is to return a vector with those $\log q$ polynomials $u_j$.

Thus, when given a vector with $n$ polynomials, it returns a vector with $n \cdot \log q$ polynomials.

Maybe this answer will be useful to you, since it is very related to your question ($Dec_{w,q}$ is a generalization of BitDecomp that uses a parameter $w$ to the base instead of fixing the value $2$).