# Fast Basis Conversion - (Mod-up, BConv, FBC) A method for converting RNS representation from one base to another base which are co-prime. This is useful for [[Mod-up]] and [[CKKS Rescale - mod_down|Mod-down]] algorithms. let $x\in\mathbb{Z}_q$ which is represented in CRT by $[x]_{q_i}$ . we would like to compute $[x]_{p_i}$. note that $x\in\mathbb{Z}_q$ implies it is smaller than $q$. also note that the integer reconstruct by [[Chinese Reminder Theorem (CRT)|CRT]] can be larger than $q$ and so it is required to compute modulo $q$ after the CRT reconstruction of an integer. This is important! $x= \bigg[\sum_{i=0}^\ell [x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\cdot \hat{q_i}\bigg]_q$ Converting the equation to be over the integers, we get: $(1)\ \ \ \ \ \ \ x=\sum_i [x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\cdot \hat{q_i} -v\cdot q$ for some integer $v$. We can approximate $v$ using the fact that $x/q<1$ for $|x|<q$ and we get $\lfloor x/q\rfloor=0$. Divide (1) by $q$ (as real number and not as inverse in $\mathbb{Z}_q$), floor and add $v$ to both sides of the equation, we get $v = \Bigg\lfloor\bigg( \sum_i [x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\cdot \hat{q_i}\bigg)/q \Bigg\rfloor=\bigg\lfloor \sum_i \frac{[x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}}{q_i}\bigg \rfloor$ Now, we ready to compute $[x]_{p_i}$, $\begin{align} [x]_{p_j}&=\bigg[\sum_{i=0}^{\ell} [x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\cdot [\hat{q_i}]_{p_j}-[v]_{p_j}\cdot[q]_{p_j}\bigg]_{p_j}\\ &= \sum_i\bigg[\big[ [x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i} \big]_{q_i}\cdot[\hat{q_i}]_{p_j}\bigg]_{p_j} - \Bigg[\bigg\lfloor\sum_i \frac{\big[[x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\big]_{q_i}}{q_i}\bigg\rfloor\Bigg]_{p_j}\cdot [q]_{p_j} \end{align}$ This computation is due Shai et.al[^1]. Note: $v$ can be computed once and reuse when computing $[x]_{p_i}$ for each $p_i$. Although in GPU implementation we compute it multiple times as there are common terms in the left sum and the right sum and we want to minimize these calls. ## RNS-HEAAN Fast base conversion formula HEAAN-RNS [^3] scheme requires all primes $q_i,p_i$ to be close to some prime $q$. More recent implementation of CKKS do not hold this requirements and the values of $q_i$ and $p_i$ are independent and can have large differences. The above requirement of HEAAN-RNS enable a simpler computation (without computing $v$) than the above and allow inaccuracy in the computation of FBC. $ [x]_{p_j}=\sum_{i=0}^{\ell}\bigg( \big[[x]_{q_i}\cdot [\hat{q_i}^{-1}]_{q_i}\big]_{q_i}\cdot [\hat{q_i}]_{p_j} \bmod {p_j}\bigg) \bmod p_j $ This computation is also mentioned in [^2] and I've implemented it here[^5] The FBC algorithm was originally introduced in [^4]. ## Created 2024-07-07 15:54 [^1]: [[@An Improved RNS Variant of the BFV Homomorphic Encryption Scheme]], section 2.2. [^2]: [Better Bootstrapping for Approximate Homomorphic Encryption](https://eprint.iacr.org/2019/688.pdf) [^3]: [A Full RNS Variant of Approximate Homomorphic Encryption](https://eprint.iacr.org/2018/931.pdf) , page 6 [^4]: [A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes](https://eprint.iacr.org/2016/510.pdf), page 5 [^5]: CKKS-RNS/tools/exp_fast_base_conversion.py in FHE_RESEARCH repository