# 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) &= a_dx^d + a_{d-1}x^d_{d-1} + ... + a_1x + a_0\\ &= \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\\ &= \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\\ &= \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) \\ &= \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 \\ &= \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$$).

• Okay, this makes much more sense than what I had in mind. Thank for the other link as well!
– sycs
Aug 17, 2016 at 0:11