A-1.5 Centered Residue Representation

Throughout this section, we have assumed that the residues are positive integers. For example, the possible residues modulo $q$ are assumed to be $\{0,1,\cdots ,q-1\}$. This system is called the canonical (i.e., unsigned) residue representation. On the other hand, there is also a counterpart system that assumes signed (i.e., centered) residues $\left\{-{\displaystyle \frac{q}{2}},-{\displaystyle \frac{q}{2}}+1,\cdots ,0,\cdots ,{\displaystyle \frac{q}{2}}-2,{\displaystyle \frac{q}{2}}-1\right\}$¹, with the residues centered around $0$, and the total number of residues is the same, namely $q$. In both systems, a modulo operation changes a given value to another value within the system’s residue range such that: (1) if the given value is greater than the upper bound of the residue range, the value is subtracted by the modulus $q$; (2) if the value is less than the lower bound of the residue range, the value is increased by the modulus $q$. The only difference between these two (canonical and centered) systems is their upper bounds and lower bounds: $0$ and $q-1$ in the canonical residue system, whereas $-{\displaystyle \frac{q}{2}}$ and ${\displaystyle \frac{q}{2}}-1$ in the centered residue system. The canonical residue representation assumes that ${\mathbb{Z}}_q=\{0,1,\cdots ,q-1\}$, whereas the centered residue system assumes that ${\mathbb{Z}}_q=\left\{-{\displaystyle \frac{q}{2}},-{\displaystyle \frac{q}{2}}+1,\cdots ,0,\cdots ,{\displaystyle \frac{q}{2}}-2,{\displaystyle \frac{q}{2}}-1\right\}$.

In both systems, the same properties hold for addition, subtraction, multiplication, and division (when the divisor is invertible). This can be proved using the reasoning from §A-1.2: any two congruent residues differ by an integer multiple of $q$ in either representation.

Also, the same property holds for an inverse: an inverse of $a$ modulo $q$ is $a^{-1}$ such that $a\cdot a^{-1}\equiv 1modq$.

Using a signed residue representation is useful in certain cases. In an example of canonical (i.e., unsigned) residue representation, suppose we have the relation $a+bmodq$ and we know that in a given application, $a+b$ is guaranteed to be within the $[0,q-1]$ range (i.e., $0\le a+b\le q-1$). Then, $(a+bmodq)$ = $a+b$, and thus we can remove the modulo operation, simplifying the relation. Now, suppose a different example of centered (i.e., signed) residue representation where we have the relation $a-bmodq$, and we know that in a given application, $a-b$ is guaranteed to be within the range $\left[-{\displaystyle \frac{q}{2}},{\displaystyle \frac{q}{2}}-1\right]$. Then, $(a-bmodq)=a-b$. However, notice that if the relation $a-bmodq$ were in a canonical residue representation, then we cannot remove the modulo operation because if $a-b$ is negative, then this becomes smaller than the lower bound of the canonical residue system (i.e., $0$), and thus a modulo reduction (i.e., addition by one or more $q$) is needed.

In §D-5.8, we design the FastBConvEx operation based on this beneficial property of centered residue representation: in this algorithm design, we can simplify $(\mu +umod{b}_{\alpha })$ to $\mu +u$ because we know that $-{\displaystyle \frac{b_{\alpha }}{2}}\le \mu +u<{\displaystyle \frac{b_{\alpha }}{2}}$.