Homomorphic Encryption and the Approximate GCD Problem Confusion Note: I asked this question on Math.StackExchange yesterday and it wasn't answered, so I thought I would repost it here, in hope of getting an answer 



I am reading Homomorphic Encryption and the Approximate GCD Problem, specifically Section 3.2 on page 23, which outlines a basic encryption scheme:


  The user chooses a large odd integer $p$ to be the secret key for the system.  
  
  A plaintext is a single bit $m$.  To encrypt a message $m\in\{0,1\}$ and obtain a ciphertext $c$, the user chooses $q,e \in\mathbb{Z}$ independently and randomly from some distribution for each encryption and computes $$E(m,p) =qp+ 2e+m$$
  
  The binary size of $q$ is generally chosen to be greater than the binary size of $p$. The binary size of $e$, which is referred to as the error, is much smaller than the binary size of $p$. We will discuss the exact sizes for these parameters later on.
  
  The decryption function for this system is given by
  $$D(c,p) = (c\mod p)\mod 2$$
  
  To see that the decryption function is correct for a ciphertext $c=qp+ 2e+m$, observe that
  \begin{align}D(c,p) &amp;= (qp+ 2e+m\mod p)\mod 2
\\&amp;= (2e+m)\mod 2\\
&amp;=m \end{align}
  
  Note that for this to work we need \begin{align}2|e|+ 1&amp;&lt;\frac p2\\|e|&amp;&lt;\frac p4−\frac 12\end{align} so that $(2e+m\mod p) = 2e+m$.


However, what I am struggling with is, if we choose $e&lt;0$ then \begin{align}2e+m\mod p &amp;= (p-2|e|)+m\\&amp;\neq2e+m\end{align} by the definition of modulo (at least as seen by most common programming languages):


  $a\mod b=r$ where $a=qb+r$ and $0\leq r&lt;b$


Since $p$ is specified to be odd, then we have 
\begin{align}&amp;((p-2|e|)+m)\mod 2 \\
&amp;=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\\
&amp;= ((1-0)+m)\mod2\tag{as $p$ is odd}\\
&amp;= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\\
&amp;\neq m\end{align}

I'm just trying to understand why we specify $$|e|&lt;\frac p4 - \frac 12$$ and not $$0&lt;e&lt;\frac p4 - \frac 12$$

as, as far as I understand, the decryption doesn't work when \begin{align}0&lt;-e&amp;&lt;\frac p4 - \frac 12\\
\frac 12 - \frac p4 &lt; e &amp;&lt; 0
\end{align}


  Example
  
  Choose $p=1583$, $q=52498$, then $|e|&lt;\frac{1583}{4}-\frac 12 = 395.25$ so choose $e=-241$
  
  For $m=1$, we have \begin{align}c&amp;=52498\times 1583+2\times (-241)+1\\
&amp;= 83104334-482+1\\
&amp;= 83103853\end{align}
  
  We decrypt this as follows \begin{align}D(c,p)&amp;=(c\mod p)\mod 2\\
&amp;= (83103853\mod 1583) \mod 2\\
&amp;= 1102 \mod 2\\
&amp;= 0\\
&amp;\neq m=1\end{align}
  
  We can see that \begin{align}(c\mod p) &amp;= 1102\\
&amp;= (2\times 550.5) + 1\end{align} and $550.5 &gt; 395.25$ which doesn't satisfy the constraint on $|e|$




Can someone either confirm that my logic is correct, or explain to me where it is falling apart please.
The reference linked states in its Notation section (page vii):


  $a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$


Thus the definition of $\bmod$ used is the non-standard
$$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;-p&lt;2r\le p$$

This can be viewed as the offset of $a$ from the nearest multiple of $p$ (with nearest selecting the lower as a tie-breaker), as suggested by a comment.

This can be programmed as r = ((a + (p-1)/2) % p) - (p-1)/2, making sure that


things are evaluated as signed integers (which in C can require some explicit casting for unsigned p);
the addition of (p-1)/2 does not cause overflow.