# How to make the range of modulo $p$ to $[-\frac{p}{2};\frac{p}{2}]$?

I am using NTL (A Library for doing Number Theory) to implement a FHE (Fully Homomorphic Encryption) scheme. In general, the range of modulo p is $[-\frac{p}{2};\frac{p}{2}]$ in FHE scheme. However, the range of modulo p is $[-p,p]$ in NTL.

If I want to use the range that is $[-\frac{p}{2};\frac{p}{2}]$, how I can do it ?

If the value $x$ is in the set $\{0, 1, 2, .., p-1\}$, which is the "natural" set of residues moduli $p$, then, you just have to check if $x$ is greater than $\frac{p}{2}$ and if so, subtract $p$.

If $x$ does not belong to $\{0, 1, 2, .., p-1\}$, then you can first do the usual modular reduction to transform $x$ in a element of this set and then, do the subtraction if needed.

my_modular(x, p)
if 0 <= x and x <= p-1
if x > p/2
return x - p
else
return x
else
new_x = x % p # usual modular operation
return my_modular(new_x, p)


Notice that I am assuming the usual modular operation will not return negative values as you are saying the NTL's mod operation does.

Try to find a modular operation that return values in $\{0, 1, 2, .., p-1\}$.

• Thanks！Before I also thought this method of transformation. But I expected there is a data type in NTL to support it. Now I can use your idea to define new data type in NTL to support the range of modulo p is [-p/2,p/2). – zhigang chen Apr 7 '16 at 1:43
• @zhigangchen does this response answers your question? If yes, please, accept it. If not, please, tell me why so I can improve it. Thanks. – Hilder Vitor Lima Pereira Apr 12 '16 at 21:27

For a prime number p, the cardinality of finite field Fp is #$F_p\;= \;p$, and $F_p=\{0,1,\cdots,p-1\}$. To define positive and negative number in $F_p$ by convention negative elements are those with most significant bit msb=1. Then with this convention, there are $\frac{p-1}{2}$ negative numbers and $\frac{p+1}{2}$ positive numbers! $F_p=[-\frac{p-1}{2}, +\frac{p+1}{2}]$

• Correction tipo: $F_p=[ -\frac{p-1}{2},+\frac{p-1}{2}]$. if p=7: then $F_p=\{4,5,6,0,1,2,3\}$ Now it's correct. – Robert NACIRI Apr 5 '16 at 9:41