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) &= (qp+ 2e+m\mod p)\mod 2 \\&= (2e+m)\mod 2\\ &=m \end{align}
Note that for this to work we need \begin{align}2|e|+ 1&<\frac p2\\|e|&<\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<0$ then \begin{align}2e+m\mod p &= (p-2|e|)+m\\&\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<b$
Since $p$ is specified to be odd, then we have \begin{align}&((p-2|e|)+m)\mod 2 \\ &=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\\ &= ((1-0)+m)\mod2\tag{as $p$ is odd}\\ &= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\\ &\neq m\end{align}
I'm just trying to understand why we specify $$|e|<\frac p4 - \frac 12$$ and not $$0<e<\frac p4 - \frac 12$$
as, as far as I understand, the decryption doesn't work when \begin{align}0<-e&<\frac p4 - \frac 12\\ \frac 12 - \frac p4 < e &< 0 \end{align}
Example
Choose $p=1583$, $q=52498$, then $|e|<\frac{1583}{4}-\frac 12 = 395.25$ so choose $e=-241$
For $m=1$, we have \begin{align}c&=52498\times 1583+2\times (-241)+1\\ &= 83104334-482+1\\ &= 83103853\end{align}
We decrypt this as follows \begin{align}D(c,p)&=(c\mod p)\mod 2\\ &= (83103853\mod 1583) \mod 2\\ &= 1102 \mod 2\\ &= 0\\ &\neq m=1\end{align}
We can see that \begin{align}(c\mod p) &= 1102\\ &= (2\times 550.5) + 1\end{align} and $550.5 > 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.
You made a couple of mistakes when you wrote this:
\begin{align}2e+m\mod p &= p-(2e+m)\\&\neq2e+m\end{align}
First of all, you seem to be assuming $e$ is negative on the left and positive on the right. Second, you subtracted $m$ as well as $2e$, but $m$ is always non-negative. The correct expression should be
\begin{align}2e+m\mod p &= (p-2|e|)+m\end{align}
You should be able to work out the rest.
INCIDENTALLY: Do NOT go by 'nearly all programming languages' when using modulo arithmetic in a purely mathematical context. The expression
\begin{align}n\mod p\end{align}
ALWAYS means the value $r$ between 0 [inclusive] and p [exclusive] such that $n - r$ is divisible by $p$, even when $n$ is negative.