# How to compute the decompositions used in fast FHE bootstrapping?

Leo Ducas and Daniele Micciancio's recent paper "FHE Bootstrapping in less than a second" gave an exciting result that one can compute the `atom operation' of Fully Homomorphic Encryption (i.e. NAND-and-Recrypt) within 1 second without loss of security. I am trying to figure out how their scheme works.

However the key technique of their bootstrapping scheme, 'Homomorphic Accumulator', uses some decomposition algorithms that may be common and trivial in the area of mathematics but I have no idea about them.

Concretely, on page 10, the Algorithm 1 states:

(For each $i$) compute the base-$B_r$ representation of $-a_i = \sum_j B_r^j \cdot a_{i,j}$ ($\mod q$)

where $j$, $B_r$ are small integers and each $a_i$ is a component of vector $\boldsymbol{a}$.

Similarly, on the next page,

On input the current accumulator content $ACC \in R^{2d_g \times 2}$... first computes the base-$B_g$ decomposition of $u^{-1}ACC = \sum_{i=1}^{d_g} B_g^{i-1} \boldsymbol{D}_i$ (where each $\boldsymbol{D}_i \in R^{2d_g \times 2}$ has entries with coefficients in $\{ \frac{1-B_g}{2}, \dots, \frac{B_g-1}{2} \}$...

My question is, how to perform these decompositions?

• Are you really asking for an algorithm to represent an integer $x$ in base $b$? That's standard stuff. Have I misunderstood your question? – D.W. Oct 13 '14 at 9:13
• I overthought the problem, D.W. you have pointed out what I once wondered. Thank you. Indeed, it is just a simple numeral system conversion. – phan Oct 14 '14 at 8:20