a12-modulus-rescaling.tex

\subsection{Rescaling Modulo of Congruence Relations}
\label{subsec:modulo-rescaling}

Remember from \autoref{sec:modulo} that $a \bmod q$ is the remainder of $a$ divided by $q$, and the congruence relation $a \equiv b \bmod q$ means that the remainder of $a$ divided by $q$ is the same as the remainder of $b$ divided by $q$. Its equivalent numeric equation is  $a = b + k\cdot q$, meaning that $a$ and $b$ differ by some multiple of $q$. The congruence and equation are two different ways of describing the relationship between two numbers $a$ and $b$. 

In this section, we introduce another way of describing the relationship between numbers. We will describe two numbers $a$ and $b$ in terms of a different modulo $q'$ instead of the original modulo $q$. Such a change of modulo in a congruence relation is called modulo scaling. When we rescale the modulo of a congruence relation, we also need to rescale the numbers involved in the congruence relation. 

Suppose we have the following congruence relations: 

$a \equiv b \bmod q$

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

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

Now, suppose we want to rescale the modulo of the above congruence relations from $q \rightarrow q'$, where $q' \mid q$ (meaning $q$ is a multiple of $q'$). Then, the accordingly updated congruence relations are as shown in \autoref{tab:rescaling}.



\begin{table}[h!]
{
\centering
\begin{tabular}{|l|l|l|}
\hline
\textbf{Congruence}  & \textbf{Rescaled Congruence Relation} & \textbf{Rescaled Congruence Relation}\\
\textbf{Relation} & \textbf{-- Exact} & \textbf{-- Approximate} \\
\hline\hline
$a \equiv b \bmod q$ & $\Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor \equiv \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ & $\Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor \cong \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor \bmod q'$\\
&(if $q$ divides both $aq'$ and $bq'$)&(if $q$ does not divide either $aq' \text{ or } bq'$)\\
\hline
$a + c \equiv b + d \bmod q$ & $\Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor \equiv \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ & $\Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor \cong \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor \bmod q'$\\
&(if $q$ divides all of $aq', bq', cq'$ and $dq'$)&(if $q$ does not divide:  $aq', bq', cq',$ or $dq'$)\\
\hline
$a \cdot c \equiv b \cdot d \bmod q$ & $\Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor  \equiv \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ & $\Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor  \cong \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor  \bmod q'$\\
&(if $q$ divides both $acq'$ and $bdq'$)&(if $q$ does not divide either  $acq'$ or $bdq'$)\\
\hline
\end{tabular} \par
}
\caption{Rescaling the congruence relations  from modulo $q\rightarrow q'$ (where $\lceil \rfloor$ denotes rounding to the nearest integer)}
\label{tab:rescaling}
\end{table}


\begin{proof}

$ $

\begin{enumerate}
%\item Let $\hat{a} = \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor$, $\hat{b} = \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor$, $\hat{c} = \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor$, $\hat{d} = \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor$, where 
\item $a \equiv b \bmod q$ $\Longleftrightarrow$ $a = b + q\cdot k$ (for some integer $k$)

$\Longleftrightarrow a \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + q\cdot k \cdot \dfrac{q'}{q}$

$\Longleftrightarrow a \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + k\cdot q'$



\begin{enumerate}
\item If $q$ divides both $aq'$ and $bq'$, then $a \cdot \dfrac{q'}{q} = \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor$, and $b \cdot \dfrac{q'}{q} = \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor$. Therefore:

$a \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor = \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor \equiv \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a \equiv b \bmod q)$

$ $

\item If $q$ does not divide either $aq'$ or $bq'$, then $a \cdot \dfrac{q'}{q} \approx \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor$, \text{ } $b \cdot \dfrac{q'}{q} \approx \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor$. Therefore:

$a \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor \approx \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor \cong \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a \equiv b \bmod q)$

\end{enumerate}

$ $

\item $a + c\equiv b + d\bmod q$ $\Longleftrightarrow$ $a + c = b + d + k\cdot q$ (for some integer $k$)

$\Longleftrightarrow a \cdot \dfrac{q'}{q} + c \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + d \cdot \dfrac{q'}{q}  + q\cdot k \cdot \dfrac{q'}{q}$

$\Longleftrightarrow a \cdot \dfrac{q'}{q} + c \cdot \dfrac{q'}{q}  = b \cdot \dfrac{q'}{q} + d \cdot \dfrac{q'}{q} + k\cdot q'$

\begin{enumerate}

\item If $q$ divides all of $aq'$, $bq'$, $cq'$, and $dq'$, then 

$a \dfrac{q'}{q} + c  \dfrac{q'}{q}  = \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor$, \text{ } $b \dfrac{q'}{q} + d \dfrac{q'}{q} = \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor$

Therefore:

$a \cdot \dfrac{q'}{q} + c \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + d \cdot \dfrac{q'}{q} + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor = \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor \equiv \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a + c \equiv b + d \bmod q)$

$ $

\item If $q$ does not divide at least one of $aq'$, $bq'$, $cq'$, and $dq'$, then

$a \dfrac{q'}{q} + c  \dfrac{q'}{q}  \approx \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor$, \text{ } $b \dfrac{q'}{q} + d \dfrac{q'}{q} \approx \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor$

Therefore:

$a \cdot \dfrac{q'}{q} + c \cdot \dfrac{q'}{q} = b \cdot \dfrac{q'}{q} + d \cdot \dfrac{q'}{q}  + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor \approx \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil a\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil c\dfrac{q'}{q}\Bigg\rfloor \cong \Bigg\lceil b\dfrac{q'}{q}\Bigg\rfloor + \Bigg\lceil d\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a + c \equiv b + d \bmod q)$

\end{enumerate}

$ $

\item $a \cdot c\equiv b \cdot d\bmod q$ $\Longleftrightarrow$ $a \cdot c = b \cdot d + k\cdot q$ (for some integer $k$)

$\Longleftrightarrow ac \cdot \dfrac{q'}{q}  = bd \cdot \dfrac{q'}{q} + q\cdot k \cdot \dfrac{q'}{q}$

$\Longleftrightarrow ac \cdot \dfrac{q'}{q}  = bd \cdot \dfrac{q'}{q} + k\cdot q'$

\begin{enumerate}

\item If $q$ divides all of $aq'$, $bq'$, $cq'$, and $dq'$, then 

$ac \cdot \dfrac{q'}{q} = \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor$, \text{ } $bd \cdot \dfrac{q'}{q} = \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor$

Therefore:

$ac \cdot \dfrac{q'}{q} = bd \cdot \dfrac{q'}{q} + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor = \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor \equiv \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a\cdot c \equiv b\cdot d \bmod q)$

$ $

\item If $q$ does not divide any of $aq'$, $bq'$, $cq'$, or $dq'$, then

$ac \cdot \dfrac{q'}{q} \approx \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor$, \text{ } $bd \cdot \dfrac{q'}{q} \approx \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor$

Therefore:

$ac \cdot \dfrac{q'}{q} = bd \cdot \dfrac{q'}{q} + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor \approx \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor + k\cdot q'$

$\Longleftrightarrow \Bigg\lceil ac\dfrac{q'}{q}\Bigg\rfloor \cong \Bigg\lceil bd\dfrac{q'}{q}\Bigg\rfloor \bmod q'$ \text{ } $(\Longleftrightarrow a\cdot c \equiv b\cdot d \bmod q)$

\end{enumerate}

$ $

\end{enumerate}
\end{proof}

As shown in the proof, if all numbers in the congruence relations are exactly divisible by the rescaling factor during the modulo rescaling, then the rescaled result gives exact congruence relations in the new modulo. On the other hand, if any numbers in the congruence relations are not divisible by the rescaling factor during the modulo rescaling (i.e., we need to round some decimals), then the rescaled result gives approximate congruence relations in the new modulo.

In a more complicated congruence relation that contains many $(+, -, \cdot)$ operations, the same principle of modulo rescaling explained above can be recursively applied to each pair of operands surrounding each operator. 

\subsubsection{Example}
\label{subsec:modulo-rescaling-ex}

Suppose we have the following congruence relation:

$b \equiv a\cdot s + \Delta \cdot m + e \bmod q$, \text{ } where: $q = 30$, \text{ } $s = 5$, \text{ } $a = 10$, \text{ } $\Delta = 10$, \text{ } $m = 1$, \text{ } $e = 10$, \text{ } $b = 40$

$ $

First, we can test if the above congruence relation is true by plugging in the given example values as follows: 

$b \equiv a\cdot s + \Delta \cdot m + e \bmod 30$

$40 \equiv 10 \cdot 5 + 10 \cdot 1 + 10 \bmod 30$

$40 \equiv 70 \bmod 30$ 

$ $

This congruence relation is true. 

$ $

Now, suppose we want to rescale the modulo from $30 \rightarrow 3$. Then, based on the rescaling principles described in \autoref{tab:rescaling}, we compute the rescaled values as follows: 

$q'= 3$, \text{ } $s = 5$, \text{ } $m = 1$

$\hat{a} = \Bigg\lceil a\cdot\dfrac{3}{30} \Bigg\rfloor = \Bigg\lceil 10\cdot\dfrac{3}{30} \Bigg\rfloor = 1$

$\hat{\Delta} = \Bigg\lceil \Delta\cdot\dfrac{3}{30} \Bigg\rfloor = \Bigg\lceil 10\cdot\dfrac{3}{30} \Bigg\rfloor = 1$



$\hat{e} = \Bigg\lceil e\cdot\dfrac{3}{30} \Bigg\rfloor = \Bigg\lceil 10\cdot\dfrac{3}{30} \Bigg\rfloor = 1$

$\hat{b} = \Bigg\lceil b\cdot\dfrac{3}{30} \Bigg\rfloor = \Bigg\lceil 40\cdot\dfrac{3}{30} \Bigg\rfloor = 4$

$ $

The rescaled congruence relation from modulo $30 \rightarrow 3$ is derived as follows:

$\Bigg\lceil b\dfrac{3}{30} \Bigg\rfloor \equiv \Bigg\lceil s\cdot a \dfrac{3}{30} \Bigg\rfloor + \Bigg\lceil m \cdot \Delta \dfrac{3}{30} \Bigg\rfloor + \Bigg\lceil e \dfrac{3}{30} \Bigg\rfloor \bmod 3$

$\hat{b} \equiv \hat{a} \cdot s + \hat{\Delta} \cdot m + \hat{e}  \bmod 3$
 \text{ } (an exact congruence relation, as all rescaled values have no decimals)

$4 \equiv 1 \cdot 5 + 1 \cdot 1 + 1 \bmod 3$

$4 \equiv 7 \bmod 3$

$ $

As shown above, the rescaled congruence relation preserves correctness, because all rescaled values are divisible by the rescaling factor. By contrast, if $\dfrac{q}{q'} = \dfrac{30}{3} = 10$ did not divide at least one of $a\cdot s$, $\Delta m$, or $e$, then the rescaled congruence relation would be an approximate (i.e., $\cong$) congruence relation.