Explicit Chinese Remainder Theorem

Let $p_i$ coprime positive integers for $i=1,...,K$. Let $a_i$ be an integer satisfying $0 \leq a_i < p_i$ for each $i$.

The Chinese Remainder Theorem (CRT) provides a way to determine an integer $a$ such that:

$a = a_1 \; mod \; p_1$

$...$

$a = a_K \; mod \; p_K$

To determine $a$, we proceed as follows. Define:

$P = p_1 \cdots p_K$

$P_i = \frac{P}{p_i}$

$t_i = P_i^{-1} \; mod \; p_i$

The value $a$ can be constructed as:

$a = \sum_{i=1}^K t_i P_i a_i$

It’s clear that $a = a_i \; mod \; p_i$ because

$t_i P_i a_i = 1 a_i = a_i \; mod \; p_i$

and

$t_i P_i a_i = 0 \; mod \; p_j \; \; \text{for} \; i \neq j$

The value $a$ is unique up to modulo $P$, but we do not know the integer $r$ for which:

$r P \leq a < (r+1)P$

For example, in lattice-based cryptography, the integer $a$ is sometimes represented as $(a_1, ..., a_K)$ for performance reasons. However, at some point, one needs to reconstruct $a$ from $(a_1, ..., a_K).$ In these cases, $|a| < P$ (in fact, $|a| < \frac{P}{2}$ because the values are centered around $0$). So, how can we reconstruct $a$?

This is where the explicit CRT (opens new window) comes into play. Let’s express $a$ a bit differently:

$a = P \sum_{i=1}^K \frac{t_i}{p_i} a_i$

We define (which is generally not an integer):

$z = \sum_{i=1}^K \frac{t_i}{p_i} a_i$

Let’s define $u$ to be congruent to $a$, satisfying

$u = a \; mod \; P, \;\;\; 0 \leq u < P$

It holds:

$Pz = u + rP$

$P(z - r) = u$

If it holds $|u| < \frac{P}{2}$, then $z-r < \frac{1}{2}$. That means:

$r = round(z)$

So we can compute $u$ as:

$u = P \cdot z - P \cdot round(z)$