I was reading the book Homomorphic Encryption and Applications when I saw a modular equation involvind non-integer numbers.

In short,

on page 59 the book define the set $y$ as $\{y_1, y_2, .., y_\Theta\}$, where each $y_i$ is a positive number smaller than 2, with $k$ bits of precision after the binary point. Then, it says that $\sum_{i \in S} y_i (\mod 2) = \frac{1}{p} - \Delta_p$, with $|\Delta_p| < 2^{-k}$.

In details, the book defines

(I) $p$ is an big odd integer

(II) each $y_i$ is of the form $\frac{u_i}{2^{k}}$

(III) where these $u_i$ have this property: $\sum_{i \in S} u_i = [ \frac{2^k}{p} ] (\mod 2^{k+1})$

Then, it says that

$\sum_{i \in S} y_i = \sum_{i \in S} \frac{u_i}{2^k} = \frac{[\frac{2^k}{p} ] + \alpha 2^{k+1}}{2^k} = \frac{[\frac{2^k}{p} ]}{2^k} + 2\alpha = \frac{1}{p} - \frac{\Delta}{2^k} + 2\alpha = \frac{1}{p} - \Delta_p (\mod 2)$

The first equality comes from (II), the third comes from (III)... It's Ok, but I don't understand the last one:

What do the authors mean with this $\mod 2$ if the equation involves non-integers values?


It means the difference between the left and right hand sides is a multiple of 2 - that is, an even whole number.

  • $\begingroup$ So, did they just use this notation to "hide" the $2\alpha$ factor on the last equality ? Thank you in advance. $\endgroup$ – Hilder Vitor Lima Pereira Dec 5 '14 at 10:57

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.