A-6.4 Gadget Decomposition

Gadget decomposition is a generalized form of number decomposition (§A-6.1). In number decomposition, a number $\gamma$ is decomposed 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}}$

In gadget decomposition, we decompose $\gamma$ as follows:

$\gamma ={\gamma }_1{g}_1+{\gamma }_2{g}_2+\cdots +{\gamma }_l{g}_l$

We denote $\overrightarrow{g}=(g_1,g_2,\cdots ,g_l)$ as a gadget vector, and ${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\overrightarrow{g}}(\gamma )=({\gamma }_1,{\gamma }_2,\cdots ,{\gamma }_l)$

Then, $\gamma =⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\overrightarrow{g}}(\gamma ),\overrightarrow{g}⟩$

In the case of number decomposition (§A-6.1), its gadget vector is $\overrightarrow{g}=({\displaystyle \frac{q}{\beta }},{\displaystyle \frac{q}{{\beta }^2}},\cdots ,{\displaystyle \frac{q}{{\beta }^l}})$.