# FHE modular reduction in specific range

I'm trying to implement a naive version of CKKS in Python. It was great until I start implementing the modulus.

For this kind of schemes, the modulus $$q$$ is in the range $$(-q/2,q/2]$$. How does this work?

In CKKS paper (I think BGV and others do the same) use something like this (a toy example): $$c = m (mod$$ $$q)$$. Where $$c$$ and $$m$$ are polynomials, so the coefficients of m are mod q. So c and m are congruent mod q.

So for each coefficient $$n$$ (if the range of mod is the typical $$[0,1,...q-1]$$), a way is to solve:

$$n = m*q + R$$

Where $$m$$ is the greatest integer that makes $$n and $$R$$ is the remainder that solves the equation being this the same reminder that for c, so n is the result for the coefficient.

But if the modulus range is other like I say, how is this done? The intuition says me that is like wrapping the number in a ''clock'' that starts in -q/2+1 and goes up to q/2 before starting again. But I don't know how to apply this intuition for negative numbers that are smaller than -q/2.

For example which is the answer of -771 (mod 1280)

If you first have some modulus function $$x\bmod q$$ that always returns a value in $$[0, q)$$, it is straightforward to switch this to your desired modulus function, for example one can define
$$x\bmod^{\pm} q := (x\bmod q) - \lfloor q/2\rfloor.$$
This is to say that to get a modulus function that returns a value in $$[c, c+q)$$ rather than $$[0,q)$$, it suffices to (manually) shift the result of calling the standard modulus function.
• Thats true. I think that Python %, implementes modulus, so thats its correct. Tell me if what I think its correct. The idea of this congruence in the new interval its that $c\equiv x\pmod q$, its to find witch $c \in (-q/2, q/2]$ has the same modulus that $m \bmod q$? For what I understand $q/2\bmod q=q/2$, but if at that I subtract $q/2$ will give me a wrong answer (for what I understand). What I'm missing? Commented Nov 21, 2022 at 15:04
• If your issue is one of the rounding boundary, i.e. $(-q/2, q/2]$ vs $[-q/2, q/2)$, you could simply add/subtract 1 from the result as necessary. Commented Nov 21, 2022 at 16:14
• @mmazz: one way to implement $c \in (-q/2, q/2]$ (given a % operation that gives a result in $[0, q)$ is $c = ((x + (q/2-1)) \% q) - (q/2-1)$ Commented Dec 19, 2022 at 19:13