Proof. $$

1.

Given $c^{\prime }=|c\cdot q^{-1}{|}_{b_{\alpha }}$, notice that $c-q\cdot c^{\prime }$ is exactly divisible by $b_{\alpha }$ as shown below:

$c-q\cdot c^{\prime }mod{b}_{\alpha }$

$=c-q\cdot |c\cdot q^{-1}{|}_{b_{\alpha }}mod{b}_{\alpha }$ $▹$ substituting $c^{\prime }=|c\cdot q^{-1}{|}_{b_{\alpha }}$

$=c-cmod{b}_{\alpha }$ $▹$ by canceling out $|q{|}_{b_{\alpha }}$ and $|q{|}_{b_{\alpha }}^{-1}$

$=0mod{b}_{\alpha }$

$$

Since $c-q\cdot c^{\prime }=0mod{b}_{\alpha }$, this implies that $c-q\cdot c^{\prime }$ is a multiple of $b_{\alpha }$ (i.e., $c-q\cdot c^{\prime }$ is exactly divisible by $b_{\alpha }$). This also implies that ${\displaystyle \frac{c-q\cdot c^{\prime }}{b_{\alpha }}}$ is an integer.

$$

2.

Given $c=|b_{\alpha }\cdot x{|}_q+\mathit{𝑢𝑞}modb$ and $c^{\prime }=|c\cdot q^{-1}{|}_{b_{\alpha }}$, we can express ${\displaystyle \frac{c-q\cdot c^{\prime }}{b_{\alpha }}}modb$ as follows:

${\left|{\displaystyle \frac{c-q\cdot c^{\prime }}{b_{\alpha }}}\right|}_b$

$={\left|{\displaystyle \frac{c-q\cdot |c\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}\right|}_b$ $▹$ by substituting $c^{\prime }=|c\cdot q^{-1}{|}_{b_{\alpha }}$

$={\left|{\displaystyle \frac{|b_{\alpha }\cdot x{|}_q+\mathit{𝑢𝑞}-q\cdot |||b_{\alpha }\cdot x{|}_q+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}\right|}_b$ $▹$ by substituting $c=||b_{\alpha }\cdot x{|}_q+\mathit{𝑢𝑞}{|}_b$

$=|{\displaystyle \frac{b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}-q\cdot ||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}{|}_b$ $▹$ by rewriting $|b_{\alpha }\cdot x{|}_q$ as $b_{\alpha }\cdot x+\mathit{𝑣𝑞}$ (where $v$ is some integer representing the $q$-overflows of $b_{\alpha }\cdot x$)

$$

$=|x+{\displaystyle \frac{\mathit{𝑣𝑞}+\mathit{𝑢𝑞}-q\cdot ||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}{|}_b$ $▹$ since $x={\displaystyle \frac{b_{\alpha }\cdot x}{b_{\alpha }}}$

$=|x+q\cdot {\displaystyle \frac{v+u-||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}{|}_b$ $▹$ taking out the common multiple $q$

$$

The above computation result is guaranteed to be an integer (as we proved in the proof step 1). And $q$ and $b_{\alpha }$ are co-prime (by the input definition). This leads to the conclusion that

${\displaystyle \frac{v+u-||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}$ is guaranteed to be an integer. Therefore, if we choose $b_{\alpha }$ (i.e., a prime and co-prime to both $q$ and $b$) as a sufficiently large value, then ${\displaystyle \frac{v+u-||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}}{b_{\alpha }}}$ will converge to $\{-1,0,1\}$. This is because as $b_{\alpha }$ increases: (1) $v$ grows slower than $b_{\alpha }$ (since $|b_{\alpha }\cdot x{|}_q=b_{\alpha }\cdot x+\mathit{𝑣𝑞}$); (2) the magnitude of $u$ stays smaller than ${\displaystyle \frac{k}{2}}+1$ (as integer $|u|\le {\displaystyle \frac{k}{2}}+1$); and (3) $||b_{\alpha }\cdot x+\mathit{𝑣𝑞}+\mathit{𝑢𝑞}{|}_b\cdot q^{-1}{|}_{b_{\alpha }}$ is guaranteed to be an integer between $\left[-{\displaystyle \frac{b_{\alpha }+1}{2}},{\displaystyle \frac{b_{\alpha }}{2}}-1\right]$. In conclusion, if $b_{\alpha }$ is sufficiently large, then we get the following relation:

${\left|{\displaystyle \frac{c-q\cdot c^{\prime }}{b_{\alpha }}}\right|}_b=x+u^{\prime }qmodb$ $▹$ where $u^{\prime }\in \{-1,0,1\}$

$$

Also, the following is true:

${\displaystyle \frac{c-q\cdot c^{\prime }}{b_{\alpha }}}modb=(c-q\cdot c^{\prime })\cdot b_{\alpha }^{-1}modb$ $▹$ because $b_{\alpha }$ divides $c-q\cdot c^{\prime }$ and $b_{\alpha }$ is co-prime to $b$

$$

3.

It is possible to express the final output $x+u^{\prime }qmodb$ as an RNS vector with the residues of the base moduli $(b_1,\cdots ,b_l)$. For this, we convert $(c-q\cdot c^{\prime })\cdot b_{\alpha }^{-1}$ into the RNS vector $(r_1,r_2,\cdots ,r_l)\in {\mathbb{Z}}_{b_1}\times {\mathbb{Z}}_{b_2}\times \cdots \times {\mathbb{Z}}_{b_l}$ by computing the following for each $i\in [1,l]$:

$r_i=|(c-q\cdot c^{\prime })\cdot b_{\alpha }^{-1}{|}_{b_i}$

$=|(c_{b_i}-|q{|}_{b_i}\cdot c^{\prime })\cdot b_{\alpha }^{-1}{|}_{b_i}$

□