0
$\begingroup$

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} $.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.