Update: have understood the digits breaking method under the HPS trick.
I am reading the digits breaking function. why it only times QHatInvModq?
let me give a simple example. if the radix set is 3,5,7,11, and the number to represent is 2257.
The third digit should be(2257-2257%(3*5)) / (3*5) mod 7.but it above code seems only times QHatInvModq
1/(3*5) mod 7. where is the left part-2257%(3*5)?
@helenpeng It looks like you’ve already answered your question. Just in case, I am still including the answer (both to confirm it is answered and also for others members of the Discourse forum).
The digit breaking function you are asking about is documented in Section B.2.3 of Revisiting Homomorphic Encryption Schemes for Finite Fields. We can use the HPS trick to simplify the computation. The HPS trick is described in Section 3.3 of An Improved RNS Variant of the BFV Homomorphic Encryption Scheme.
Please let me know if this fully answers your question and matches your understanding.
Yes, i also find the HPS trick in your mentioned papers. This trick not only can reduce the substract and mod operations, but also can avoid the dependencies across digits, which may can be accelerated in parallel.