a01-modulo.tex

\noindent \textbf{- Reference} 

\href{https://www.youtube.com/watch?v=fz1vxq5ts5I}{YouTube -- Extended Euclidean Algorithm Tutorial}.


\subsection{Overview}
\label{subsec:modulo-overview} 

\begin{tcolorbox}[title={\textbf{\tboxdef{\ref*{subsec:modulo-overview}} Integer Modulo}}]

\begin{itemize}

\item \textbf{Modulo} is the operation of computing the remainder obtained when one number is divided by another. \textbf{modulo} is often abbreviated as \textbf{mod}.

$ $

\item \textbf{$\bm{a}$ mod $\bm{q}$ (i.e., $\bm{a} \bm{\text{ modulo } q}$)} is the remainder after dividing $a$ by $q$, which is always an element of $\{0, 1, 2, 3, \cdots, q-1\}$. For example, $7 \bmod 5 = 2$, because the remainder of dividing 7 by 5 is 2. 

$ $

\item \textbf{Modulus:} Given $\bm{a}$ mod $\bm{q}$, we call the divisor $q$ the modulus, whereas \emph{modulo} refers to the operation.

$ $

\item \textbf{Modulo Congruence ($\bm{\equiv}$):} $a$ is congruent to $b$ modulo $q$ (i.e., $a \equiv b \textbf{ mod } q$) if they have the same remainder when divided by $q$. For example, $5 \equiv 12 \bmod 7$, because $5 \bmod 7 = 5$ and $12 \bmod 7 = 5$. In mathematics, the notation $a \equiv b \bmod q$ is identical to $a = b \pmod q$, meaning that the remainder of $a$ divided by $q$ is the same as the remainder of $b$ divided by $q$. Note that this notation differs from $a = b \bmod q$, which states that $a$ equals the remainder of $b$ divided by $q$.

$ $

\item \textbf{Congruence \textit{vs.} Equality:} 

$a \equiv b \bmod q \Longleftrightarrow a = b + k\cdot q$ \text{ } (for some integer $k$)

$ $

This means that $a$ and $b$ are congruent modulo $q$ if and only if $a$ and $b$ differ by some multiple of $q$. For example, $5 \equiv 12 \bmod 7 \Longleftrightarrow 5 = 12 + (-1)\cdot 7$

\end{itemize}

\end{tcolorbox}


\subsection{Modulo Arithmetic}
\label{subsec:modulo-arithmetic}

The supported modulo operations are addition, subtraction, and multiplication. The properties of these modulo operations are as follows:

\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:modulo-arithmetic}.1} Properties of Modulo Operations}}]
For any integer $x$, the following is true:

\begin{enumerate}
\item \textbf{Addition:} $a \equiv b \bmod q \Longleftrightarrow a + x\equiv b + x\bmod q$

\item \textbf{Subtraction:} $a \equiv b \bmod q \Longleftrightarrow a - x\equiv b - x\bmod q$

\item \textbf{Multiplication:} $a \equiv b \bmod q \Longleftrightarrow a \cdot x \equiv b \cdot x \bmod q$. 
This equivalence holds provided that $\gcd(x,q)=1$. Without this assumption, only the implication $a \equiv b \bmod q \Rightarrow a \cdot x \equiv b \cdot x \bmod q$ is guaranteed.

\end{enumerate}

\end{tcolorbox}

\begin{proof}

$ $

For any integer $x$,

\begin{enumerate}


\item \textbf{Addition:} $a \equiv b \bmod q \Longleftrightarrow a = b + k q $ (for some integer $k$) \textcolor{red}{ \text{ } \# $a$ and $b$ differ by some multiple of $q$}

$\Longleftrightarrow a + x = b + k\cdot q + x$

$\Longleftrightarrow a + x = b + x + k\cdot q$ \textcolor{red}{ $\rhd$ $a+x$ and $b+x$ differ by some multiple of $q$}

$\Longleftrightarrow a + x \equiv b + x \bmod q$

$ $

\item \textbf{Subtraction:} $a \equiv b \bmod q \Longleftrightarrow a = b + k q $ (for some integer $k$)

$\Longleftrightarrow a - x = b + k\cdot q - x$

$\Longleftrightarrow a - x = b - x + k\cdot q$  \textcolor{red}{ $\rhd$ $a-x$ and $b-x$ differ by some multiple of $q$}

$\Longleftrightarrow a - x \equiv b - x \bmod q$

$ $

\item \textbf{Multiplication:} $a \equiv b \bmod q \Longleftrightarrow a = b + k q $ (for some integer $k$)

$\Longrightarrow a \cdot x = b \cdot x + k\cdot q \cdot x$

$\Longrightarrow a \cdot x = b \cdot x + k_x\cdot q$ (where $k_x = k \cdot x$)  \textcolor{red}{ $\rhd$ $a\cdot x$ and $b\cdot x$ differ by some multiple of $q$}

$\Longrightarrow a \cdot x \equiv b \cdot x \bmod q$

Conversely, if $x$ and $q$ are coprime (i.e., $\gcd(x,q)=1$), then $x$ has a multiplicative inverse $x^{-1}$ modulo $q$. From $a \cdot x \equiv b \cdot x \bmod q$

$\Longrightarrow a \cdot x \cdot x^{-1} \equiv b \cdot x \cdot x^{-1} \bmod q$

$\Longrightarrow a \equiv b \bmod q$

\end{enumerate}
\end{proof}

Based on the modulo operations in Theorem~\ref*{subsec:modulo-arithmetic}.1, we can also derive the following properties of modulo arithmetic:


\begin{tcolorbox}[title={\textbf{\tboxtheorem{\ref*{subsec:modulo-arithmetic}.2} Properties of Modulo Arithmetic}}]

\begin{enumerate}
\item \textbf{Associative:} $(a \cdot b) \cdot c \equiv a \cdot (b \cdot c) \bmod q$

\item \textbf{Commutative:} $(a \cdot b) \equiv (b \cdot a) \bmod q$

\item \textbf{Distributive:} $(a \cdot (b + c)) \equiv ((a \cdot b) + (a \cdot c))  \bmod q$

\item \textbf{Interchangeable:} Congruent values are interchangeable in modulo arithmetic. 

For example, suppose $(a \equiv b \bmod q)$ and $(c \equiv d \bmod q)$. Then, $a$ and $b$ are interchangeable, and $c$ and $d$ are interchangeable in modulo arithmetic as follows:

$(a + c) \equiv (b + d) \equiv (a + d) \equiv (b + c) \bmod q$

$(a - c) \equiv (b - d) \equiv (a - d) \equiv (b - c) \bmod q$

$(a \cdot c) \equiv (b \cdot d) \equiv (a \cdot d) \equiv (b \cdot c) \bmod q$

\end{enumerate}

\end{tcolorbox}

The proof of Theorem~\ref*{subsec:modulo-arithmetic}.2 is similar to that of Theorem~\ref*{subsec:modulo-arithmetic}.1, which we leave as an exercise for the reader. 


\subsection{Inverse}
\label{subsec:modulo-inverse}

\begin{tcolorbox}[title={\textbf{\tboxdef{\ref*{subsec:modulo-inverse}} Inverse in Modulo Arithmetic}}]

In modulo $q$ (i.e., in the world of remainders where all numbers have been divided by $q$), for each $a \in \{0, 1, 2, \cdots, q-1\}$:

\begin{itemize}

\item \textbf{Additive Inverse} of $a$ is denoted as $a_+^{-1}$ which satisfies $a + a_+^{-1} \equiv 0 \bmod q$. For example, in modulo 11, $3_+^{-1} = 8$, because $3 + 8 \equiv 0 \bmod 11$.

\item \textbf{Multiplicative Inverse} of $a$ is denoted as $a_*^{-1}$ which satisfies $a \cdot a_*^{-1} \equiv 1 \bmod{q}$. Such an inverse exists if and only if $\gcd(a,q)=1$. For example, modulo 11, $3_*^{-1} = 4$, because $3 \cdot 4 \equiv 1 \bmod{11}$.

\end{itemize}

\end{tcolorbox}

\subsection{Modulo Division}
\label{subsec:modulo-division}

In modulo arithmetic, \textit{modulo division} is different from regular numeric division. Strictly speaking, there is no separate operation called “modulo division”, because the modulo operation already returns only the remainder of a division. In practice, one uses “modulo division” to mean multiplying by a modular inverse when it exists, i.e., when $\gcd(a,q)=1$. \textit{Modulo division} of $b$ by $a$ modulo $q$ is equivalent to computing the \textit{modular} multiplication $b \cdot a^{-1} \bmod q$. The result of \textit{modulo division} is different from that of numeric division because \textit{modulo division} always gives an integer (a residue modulo $q$) (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 (\href{https://www.youtube.com/watch?v=fz1vxq5ts5I}{YouTube tutorial}).

\subsection{Centered Residue Representation}
\label{subsec:modulo-centered}

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\{-\dfrac{q}{2}, -\dfrac{q}{2} + 1, \cdots, 0, \cdots, \dfrac{q}{2} - 2, \dfrac{q}{2} - 1\right\}$\footnote{Here, we assume $q$ is an even number. In the case where $q$ is an odd number, the residues are $\left\{ -\dfrac{q-1}{2}, -\dfrac{q-3}{2}, \cdots, 0, \cdots, \dfrac{q-3}{2}, \dfrac{q-1}{2}\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 $-\dfrac{q}{2}$ and $\dfrac{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\{-\dfrac{q}{2}, -\dfrac{q}{2} + 1, \cdots, 0, \cdots, \dfrac{q}{2} - 2, \dfrac{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 \autoref{subsec:modulo-arithmetic}: 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 1 \bmod q$. 

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 + b \bmod q$ and we know that in a given application, $a + b$ is guaranteed to be within the $[0, q-1]$ range (i.e., $0 \leq a + b \leq q-1$). Then, $(a + b \bmod q)$ = $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 - b \bmod q$, and we know that in a given application, $a - b$ is guaranteed to be within the range $\left[-\dfrac{q}{2}, \dfrac{q}{2} - 1\right]$. Then, $(a - b \bmod q) = a - b$. However, notice that if the relation $a - b \bmod q$ 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 \autoref{subsec:rns-fastbconvex}, we design the \textsf{FastBConvEx} operation based on this beneficial property of centered residue representation: in this algorithm design, we can simplify $(\mu + u \bmod b_\alpha)$ to $\mu + u$ because we know that $-\dfrac{b_\alpha}{2} \leq \mu + u < \dfrac{b_\alpha}{2}$.