A-6.1 Number Decomposition

Suppose we have the number $\gamma$ modulo $q$. Number decomposition expresses $\gamma$ as a sum of multiple numbers in base $\beta$ as follows:

$\gamma ={\gamma }_1{\displaystyle \frac{q}{{\beta }^1}}+{\gamma }_2{\displaystyle \frac{q}{{\beta }^2}}+\cdots +{\gamma }_l{\displaystyle \frac{q}{{\beta }^l}}$

, where each of the ${\gamma }_i$ term represents a base-$\beta$ value shifted $i$ bits (which is a multiple of ${\text{log}}_2\beta$) to the left. We call $l$ the level of decomposition. This is visually shown in Figure 1.

We define the decomposition of number $\gamma$ into base $\beta$ with level $l$ as follows:

${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(\gamma )=({\gamma }_1,{\gamma }_2,\cdots ,{\gamma }_l)$.

Number decomposition is also called radix decomposition, where the base $\beta$ is called a radix.

A-6.1.1 Example

Suppose we have the number $\gamma =13modq$, where $q=16$. Suppose we want to decompose 13 with the base $\beta =2$ and level $l=4$. Then, 13 is decomposed as follows:

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

${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{2,4}(13)=(1,1,0,1)$