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 }_{\ell }{\displaystyle \frac{q}{{\beta }^{\ell }}}$

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

$\gamma ={\gamma }_1{g}_1+{\gamma }_2{g}_2+\cdots +{\gamma }_{\ell }{g}_{\ell }$

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

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 }^{\ell }}})$.