FHE modular reduction in specific range

Question

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<m*q$ 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)

Answer 1

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.