According to Section 2.3 of Full-RNS CKKS:
More precisely, for a basis $ \left\{p_{0}, \ldots, p_{k-1}, q_{0}, \ldots, q_{\ell-1}\right\} $, let $ \mathcal{B}=\left\{p_{0}, \ldots, p_{k-1}\right\} $ and $ \mathcal{C}=\left\{q_{0}, \ldots, q_{\ell-1}\right\} $ be its subbases. Let us denote their products by $ P= \prod_{i=0}^{k-1} p_{i} $ and $ Q=\prod_{j=0}^{\ell-1} q_{j} $, respectively. Then one can convert the RNS representation $ [a]_{\mathcal{C}}=\left(a^{(0)}, \ldots, a^{(\ell-1)}\right) \in \mathbb{Z}_{q_{0}} \times \cdots \times \mathbb{Z}_{q_{\ell-1}} $ of an integer $ a \in \mathbb{Z}_{Q} $ into an element of $ \mathbb{Z}_{p_{0}} \times \cdots \times \mathbb{Z}_{p_{k-1}} $ by computing $$ > \operatorname{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}\left([a]_{\mathcal{C}}\right)=\left(\sum_{j=0}^{\ell-1}\left[a^{(j)} \cdot \hat{q}_{j}^{-1}\right]_{q_{j}} \cdot \hat{q}_{j}\left(\bmod p_{i}\right)\right)_{0 \leq i<k} > $$ where $ \hat{q}_{j}=\prod_{j^{\prime} \neq j} q_{j^{\prime}} \in \mathbb{Z} $.
I implemented FastBConv in Mathematica:
ClearAll["Global`*"];
FastBconv[aq_List, q_List, p_List] :=
Module[{prodq, hatq, hatqinv, aP, ap},
prodq = Times @@ q;
hatq = prodq/q;
hatqinv = ModularInverse[hatq[[#]], q[[#]]] & /@ Range[1, Length[q]];
Print["hatq: ", hatq];
Print["hatqinv: ", hatqinv];
Print["hatq*hatqinv mod q: ", Mod[hatq*hatqinv, q]];
aP = Sum[
Mod[aq[[i]]*hatqinv[[i]], q[[i]]]*hatq[[i]], {i, 1,
Length[q]}];
ap = Mod[aP, p];
ap];
FastBconv::usage = "FastBconv[x,Q_List,P_List] Conv x(in Q_List) to P_List";
Print[FastBconv[{1,1,1},{3,5,7},{2,3}]];
Output:
: hatq: {35, 21, 15}
: hatqinv: {2, 1, 1}
: hatq*hatqinv mod q: {1, 1, 1}
: {0, 1}
However, the correct result should be:
Print[Mod[ChineseRemainder[{1,1,1}, {3,5,7}],{2,3}]];
Output:
{1, 1}
But I can't find where I went wrong in my implementation. Is my understanding of the formula incorrect? I believe that the part $ \sum_{j=0}^{\ell-1}\left[a^{(j)} \cdot \hat{q}_{j}^{-1}\right]_{q_{j}} \cdot \hat{q}_{j} $ in the formula is independent of P. I think $ \hat{q}_{j}^{-1} $ is the modular inverse of $ \hat{q_{j}} $ with respect to $ q^{j} $.
