Hi!
I’ve found that the ModRaise step of ckks-bootstrapping done in ckksrns-fhe.cpp calls the function SwitchModulus in mubintvecnat.cpp. I have two questions about this procedure.
I can’t understand the high level mathmetical meaning of the following pseudocode copied from the comment, especially the two if judgements.
And thus, I can’t understand why such SwitchModulus procedure performs the ModRaise step.
Great thanks for you help!
Some background information to help you understand this logic.
For a positive integer modulus q \in \mathbb{Z^+}, the ring \mathbb{Z}_q is identified with its representation as integers in [-q/2, q/2). Apparently, this is a signed representation that caters to both positive and negative numbers in a dynamic range of size q. In OpenFHE implementation, we use unsigned integers as datatypes to represent these values. The first half of the range is reserved for positive integers, whereas the second half is reserved for negative integers. That is, elements of \mathbb{Z}_q that are larger than q/2 are actually negative numbers and that should be taken care of when switching from one modulus to another.
As a simple example,
The ring \mathbb{Z}_5 can be viewed as {0,1,2,3,4} in the unsigned integer representation (that is in OpenFHE implementation), but this set actually represents unsigned and signed values as follows {0,1,2,-2,-1} // the lower half \{0,1,2\} is used for positive numbers and the upper half (minus 1 since q is an odd number in this case) \{3,4\} is used for neg numbers.
Say we want to switch 3 \pmod 5 to a new modulus 7.
3 \pmod 5 actually means -2 \pmod 5
3 \pmod 5 = -2 \pmod 5, // because 3 > 5/2
then
-2 \pmod 7 = 5 \pmod 7
5 above is 3+|7-5|.
