A-6.1 Number Decomposition

We fix a modulus $q\ge 2$ and write ${\mathbb{Z}}_q=\mathbb{Z}∕\mathit{𝑞\mathbb{Z}}$. Let $\gamma \in {\mathbb{Z}}_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 }_{\ell }{\displaystyle \frac{q}{{\beta }^{\ell }}}$

where $\beta \ge 2$ is a base and $\ell \ge 1$ is the decomposition level. We assume ${\beta }^{\ell }\mid q$ and take digits ${\gamma }_i\in \{0,1,\dots ,\beta -1\}$; under these conditions, the decomposition is unique. This is visually shown in Figure 1. (If ${\beta }^{\ell }\nmid q$, see §A-6.3.) Each ${\gamma }_i$ is a digit in the base-$\beta$ representation of $\gamma$, where $i=1$ is the most significant digit. When $q$ is a power of two, this corresponds to a shift by $i\cdot {\log <!--\; FUNCTION\; APPLICATION\; -->}_2\beta$ bits.

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

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

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

A-6.1.1 Example

Suppose we take $\gamma =13$ in ${\mathbb{Z}}_{16}$. Suppose we want to decompose 13 with the base $\beta =2$ and level $\ell =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)$