A-1.2 Modulo Arithmetic

Based on the modulo operations in Theorem A-2.1.1, we can derive the following properties of modulo arithmetic:

The proof of Theorem A-2.1.2 is similar to that of Theorem A-2.1.1, which we leave as an exercise for the reader.

A-1.2.1 Inverse

A-1.2.2 Modulo Division

In modulo arithmetic, modulo division is different from regular numeric division. Strictly speaking, there is no such thing as modulo division because the modulo operation itself is a form of division that returns only the remainder. modulo division of $b$ by $amodq$ is equivalent to computing the modulo multiplication $b\cdot a_{\ast }^{-1}modq$. The result of modulo division is different from that of numeric division, because modulo division always gives an integer (as it multiplies two integers modulo $q$), whereas numeric division gives a real number. The inverse of an integer modulo $q$ can be computed using the extended Euclidean algorithm (YouTube tutorial)

A-1.2.3 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\}$, where the residues are 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 bigger than the upper bound of the residue range, the value is subtracted by the modulus $q$; (2) if the value is smaller than the lower bound of the residue range, the value is added 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 modulo property of addition, subtraction, multiplication, and division holds, which can be proved by applying the same reasoning described in §A-1.2: the same properties hold in both systems because any two congruent residues in the centered system are separated by the $\mathit{𝑘𝑞}$ gaps (for some integer $k$) in both systems.

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