4
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – zhigang chen Apr 7 '16 at 1:43
  • $\begingroup$ @zhigangchen does this response answers your question? If yes, please, accept it. If not, please, tell me why so I can improve it. Thanks. $\endgroup$ – Hilder Vitor Lima Pereira Apr 12 '16 at 21:27
0
$\begingroup$

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}]$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Robert NACIRI Apr 5 '16 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.