The Chinese Remaindering Algorithm

We start with the elementary case of the Chinese Remaindering Theorem (Theorem 1). Then we give a much more abstract version (Theorem 2). Then we state the Chinese Remaindering Theorem and the Chinese Remaindering Algorithm in the context of Euclidean domains.

Theorem 1 (Sun-Tsu, first century AD)   Let $m$ and $n$ be two relatively prime integers. Let $s, t \in {\mbox{${\mathbb{Z}}$}}$ be such that $s \, m + t \, n = 1$ . For every $a, b \in {\mbox{${\mathbb{Z}}$}}$ there exists $c \in {\mbox{${\mathbb{Z}}$}}$ such that

$$(\forall x \in {\mbox{${\mathbb{Z}}$}}) \ \ \ \ \ \left\{ \begin{... ...uiv b \mod{\, n} \\ \end{array} \right. \ \ \iff \ \ x \equiv c \mod{\, m \, n}$$ (45)

where a convenient $c$ is given by

$$c \ = \ a + (b - a) \, s \, m = b + (a - b) t\, n$$ (46)

Therefore for every $a, b \in {\mbox{${\mathbb{Z}}$}}$ the system of equations

$$\left\{ \begin{array}{l} x \equiv a \mod{\, m} \\ x \equiv b \mod{\, n} \\ \end{array} \right.$$ (47)

has a solution.

Proof. First observe that Relation (46) implies

$$c \equiv a \mod{\, m} \ \ \ \ \ \ \ \ {\rm and} \ \ \ \ \ \ \ \ c \equiv b \mod{\, n}.$$ (48)

Now assume that $x \equiv c \mod{\, m \, n}$ holds. This implies

$$x \equiv c \mod{\, m} \ \ \ \ \ \ \ \ {\rm and} \ \ \ \ \ \ \ \ x \equiv c \mod{\, n}$$ (49)

Thus Relations (48) and (49) lead to

$$x \equiv a \mod{\, m} \ \ \ \ \ \ \ \ {\rm and} \ \ \ \ \ \ \ \ x \equiv b \mod{\, n}$$ (50)

Conversly

• $x \equiv a \mod{\, m}$ implies $x \equiv c \mod{\, m}$ that is $m$ divides $x - c$ and
• $x \equiv b \mod{\, n}$ implies $x \equiv c \mod{\, n}$ that is $n$ divides $x - c$ .

Since $m$ and $n$ are relatively prime it follows that $m \, n$ divides $x - c$ . (Gauss Lemma). $\qedsymbol$

Theorem 2   Let $R$ be a commutative ring with unity and $I_0, I_1, \ldots , I_{n-1}$ be ideals of $R$ . We consider the direct product of residue class rings $R/{I_0} \times \cdots \times R/{I_{n-1}}$ (additions and multiplications are computed componentwise) together with the homomorphism

$$M: \begin{array}{lll} R & \rightarrow & R/{I_0} \times \cdots \ti... ...ngmapsto & ({\overline{r}}^{I_0}, \ldots, {\overline{r}}^{I_{n-1}}) \end{array}$$ (51)

Then we have

• The kernel of $M$ is $(\cap_{i = 0}^{n-1} I_i)$ .
• If the tuple $({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}}) \in R/{I_0} \times \cdots \times R/{I_{n-1}}$ has a pre-image $r \in R$ then we have

  $$(\forall \ i,j ) \ (0 \leq i < j \leq n-1) \ \Longrightarrow \ {\overline{r_i}}^{I_i + I_j} \ = \ {\overline{r_j}}^{I_i + I_j}$$ (52)

  
  

• $M$ is surjective iff for every $i,j$ such that $0 \leq i < j \leq n-1$ we have $I_i + I_j = R$ .

Proof. The first statement is obvious. Let us prove the second one. Let $r, r_0, r_1 , \ldots, r_{n-1}$ be in $R$ . We look for the pre-image of $({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}})$ . Hence we look for $r$ such that

$$M(r) = ({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}})$$ (53)

that is

$$({\overline{r}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}}) \ = \ ({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}})$$ (54)

or

$${\overline{r - r_0}}^{I_0} \ = \ {\overline{r - r_1}}^{I_1} \ = \ \cdots \ = \ {\overline{r - r_{n-1}}}^{I_{n-1}} = 0.$$ (55)

At this point of the proof we need the following lemma. $\qedsymbol$

Lemma 1   Let $a, b$ be two elements of the ring $R$ (again commutative and with unity). Let $I, J$ be two ideals of $R$ such that ${\overline{a}}^I = {\overline{b}}^J$ . Then we have

$${\overline{a}}^{I+J} = {\overline{b}}^{I+J}$$ (56)

Proof. The equation ${\overline{a}}^I = {\overline{b}}^J$ means that the residue classe of $a$ in $R/I$ is equal to the residue classe of $b$ in $R/J$ . More formally we have

$$\{ x \in R \ \mid \ a - x \in I \} \ = \ \{ x \in R \ \mid \ b - x \in J \}$$ (57)

or equivalently

$$\{ x \in R \ \mid \ (\exists u \in I) \ \mid \ x = a + u \} \ = \ \{ x \in R \ \mid \ (\exists v \in I) \ \mid \ x = b + v \}$$ (58)

Since these sets are non empty this implies

$$(\exists (u,v) \in I \times J) \ \mid \ a + u = b + v.$$ (59)

Since $J$ is an ideal we have $-v \in J$ and thus

$$a - b \in I + J$$ (60)

The lemma is proved. $\qedsymbol$

CONTINUING THEOREM'S

Proof. With the previous lemma Relation (55), for all $i,j$ such that $0 \leq i < j \leq n-1$ holds, leads to

$${\overline{r - r_i}}^{I_i + I_j} \ = \ {\overline{r - r_j}}^{I_i + I_j}$$ (61)

or equivalently

$${\overline{r_i}}^{I_i + I_j} = {\overline{r_j}}^{I_i + I_j}.$$ (62)

Relation (62) is a necessary condition for the existence of a pre-image of $r$ via the homomorphism $M$ . Therefore we proved the second statement of the theorem. Let us prove the third one.

Let us ssume first that $M$ is surjective. Let $i,j$ be such that $0 \leq i < j \leq n-1$ . There exists $r \in R$ such that

$${\overline{r}}^{I_i} \ = \ {\overline{1}}^{I_i} \ \ \ \ {\rm and} \ \ \ \ {\overline{r}}^{I_j} \ = \ {\overline{0}}^{I_j}$$ (63)

Hence

$$1 - r \in I_i \ \ \ \ {\rm and} \ \ \ \ r \in I_j$$ (64)

which implies $I_i + I_j = 1$ . Conversly, let us assume that the ideals $I_0, \ldots , I_{n-1}$ are pairwise coprime. Let $i$ be in the range $0 \cdots n-1$ and consider the product $I$ of all ideals $I_0, \ldots , I_{n-1}$ except $I_i$ . It is a classical result that $I_i$ and $I$ are coprime. Let $u_i \in I_i$ and $v_i \in I$ such that $u_i + v_i = 1$ . Observe that for all $j = 0 \cdots n-1$ we have

$${\overline{v_i}}^{I_i} \ = \ {\overline{1}}^{I_i} \ \ \ \ {\rm an... ...\ j \neq i \ \Longrightarrow {\overline{v_i}}^{I_j} \ = \ {\overline{0}}^{I_j}.$$ (65)

Now consider $({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}}) \in R/{I_0} \times \cdots \times R/{I_{n-1}}$ . Then

$$r \ = \ v_0 r_0 + \cdots + v_{n-1} r_{n-1}$$ (66)

satisfies

$$M(r) = ({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}})$$ (67)

This concludes the proof of the theorem. $\qedsymbol$

Corollary 1   Let $R$ be a commutative ring with unity and $I_0, \ldots , I_{n-1}$ be ideals of $R$ such that we have $I_i + I_j = R$ for every $i,j$ with $0 \leq i < j \leq n-1$ . Let $I$ be the product of the ideals $I_0, \ldots , I_{n-1}$ . Then we have the ring isomorphism

$$R/I \ \simeq \ R/{I_0} \times \cdots \times R/{I_{n-1}}$$ (68)

and the group isomorphism of the multiplicative groups

$${(R/I)}^{\ast} \ \simeq \ {(R/{I_0})}^{\ast} \times \cdots \times {(R/{I_{n-1}})}^{\ast}$$ (69)

Proof. The following ring isomorphism follows from Theorem 2

$$R/({\cap}_{0 \leq i \leq n-1} I_i) \ \simeq \ R/{I_0} \times \cdots \times R/{I_{n-1}}$$ (70)

It is a well known fact that if the ideals $I_0, \ldots , I_{n-1}$ are pairwise coprime ( $I_i + I_j = R$ for every $i,j$ with $0 \leq i < j \leq n-1$ ) then their product is equal to their intersection [van91]. Therefore, we have the ring isomorphism of the statement. The group isomorphism follows from the previous ring isomorphism and the fact that the element

$$({\overline{r_0}}^{I_0}, \ldots, {\overline{r_{n-1}}}^{I_{n-1}}) \ \in \ R/{I_0} \times \cdots \times R/{I_{n-1}}$$ (71)

is a unit iff every ${\overline{r_{i}}}^{I_{i}}$ is a unit of $R/{I_i}$ . $\qedsymbol$

From now on $R$ denotes an Euclidean domain.

Corollary 2   Let $m_0, \dots, m_{n-1}$ be $n$ elements pairwise coprime in the Euclidean domain $R$ . (Hence, for all $0 \leq i < j < n$ we have ${\gcd}(m_i, m_j) = 1$ .) Let $m = m_0 \cdots m_{r-1}$ . Then, we have the ring isomorphism

$$R/m \ \simeq \ R/{m_0} \times \cdots \times R/{m_{n-1}}$$ (72)

and the group isomorphism of the multiplicative groups

$${(R/m)}^{\ast} \ \simeq \ {(R/{m_0})}^{\ast} \times \cdots \times {(R/{m_{n-1}})}^{\ast}$$ (73)

Proof. These are well known facts in an Euclidean domain $R$ .

• Every ideal $I$ of $R$ is generated by a single element. (That is, there exists an element $r \in R$ such that $I$ is the set of the multiples of $r$ denoted by ${\langle} r {\rangle}$ .)
• Two ideals ${\langle} r {\rangle}$ and ${\langle} s {\rangle}$ are coprime iff ${\gcd}(r, s) = 1$ .

Then the ring isomorphism and the groups isomorphism follow from Corollary 1 by considering the ideals $I_0 = {\langle} m_0 {\rangle}$ , ... $I_{n-1} = {\langle} m_{n-1} {\rangle}$ . $\qedsymbol$

Algorithm 4  

Proof. Assume that the algorithm terminates without error, that is the case if every $g_i$ is the gcd of $m_i$ and $\frac{m}{m_i}$ (which are assumed to be coprime). Then, for $i = 0 \cdots n-1$ we have

$$u_i \, m_i + v_i \frac{m}{m_i} \ = \ 1$$ (74)

Hence

$$r_i v_i \frac{m}{m_i} \ \ \ \equiv \ \ \ r_i \mod{ \, m_i}$$ (75)

and for $j = 0 \cdots n-1$ with $j \neq i$ we have

$$r_i v_i \frac{m}{m_i} \ \ \ \equiv \ \ \ 0 \mod{ \, m_j}$$ (76)

The specification of Algorithm 4 follow easily from Relation (75) and (76). $\qedsymbol$

Remark 6   It is important to observe that Algorithm 4 computes a solution $r$ of the system of equations given by

$$r \equiv r_i \mod{\, m_i} \ \ {\rm for} \ i = 0 \cdots n-1$$ (77)

Any other solution $r'$ of (77) satisfies $r \equiv r' \mod{\, m}$ where $m$ is the product of the moduli $m_0, \ldots, m_{r-1}$ . This follows from the fact the $m_i$ 's are pairwise coprime and from Corollary 2. Therefore the set all solutions of (77) is of the form

$$\{ r + k \, m \ \mid \ k \in R \}$$ (78)

However, in practice, we need only one solution. In the next two results (Theorem 3 and Theorem 4) by imposing

$$d(r) \ < \ d(m)$$ (79)

where $d$ is the Euclidean size of $R$ , we manage to restrict to a unique solution.

Theorem 3   Let $R = {\bf k}[x]$ for a field ${\bf k}$ . Let $m_0, \ldots, m_{r-1} \in R$ be polynomials pairwise coprime ( ${\gcd}(m_i, m_j) = 1$ for $0 \leq i < j \leq r-1$ ). Let $m$ be their product. For $0 \leq i \leq r-1$ let $d_i \geq 1$ be the degree of $m_i$ and $n = {\Sigma}_{i=0}^{r-1} d_i$ be the degree of $m$ . For $0 \leq i \leq r-1$ let $f_i \in {\bf k}[x]$ be a polynomial with degree ${\deg}(f_i) < d_i$ . Then there is a unique polynomial $f \in {\bf k}[x]$ such that

$${\deg}(f) < n \ \ \ \ {\rm and} \ \ \ \ f \equiv f_i \mod{\, m_i} \ \ {\rm for} \ \ i = 0 \cdots r-1.$$ (80)

Moreover it can be computed in ${\cal O}(n^2)$ operations in ${\bf k}$ .

Proof. Except for the complexity result (that can be found in [GG99] as Theorem 5.7) and the uniqueness, this theorem follows from Algorithm 4. The uniqueness follows from the constraint ${\deg}(f) < n$ . Indeed, assume that there are two polynomials $f$ and $g$ solutions of (80). Then we have

$$f \equiv g \mod{\, m_i} \ \ {\rm for} \ \ i = 0 \cdots r-1.$$ (81)

and thus

$$f \equiv g \mod{\, m}$$ (82)

Hence $m$ divides $f - g$ although ${\deg}(m) = n > {\deg}(f-g)$ holds. Therefore $f = g$ . $\qedsymbol$

Theorem 4   Let $m_0, \ldots, m_{r-1}, m$ be in $R = {\mbox{${\mathbb{Z}}$}}$ such that the $m_i$ 's are pairwise coprime and $m$ is their product. Let $n$ be the word length of $m$ . Let $a_0, \ldots, a_{r-1} \in R$ be such that $0 \leq a_i < m_i$ for $i = 0 \cdots r-1$ . Then there is a unique $a \in R$ such that

$$0 \leq a < m \ \ \ \ {\rm and} \ \ \ \ a \equiv a_i \mod{\, m_i} \ \ {\rm for} \ \ i = 0 \cdots r-1.$$ (83)

Moreover it can be computed in ${\cal O}(n^2)$ word operations.

Proof. Except for the complexity result (that can be found in [GG99] as Theorem 5.8) and the uniqueness, this theorem follows from Algorithm 4. The proof of the uniqueness is quite easy to establish. $\qedsymbol$

We reproduce below the ALDOR code for the Chinese Remaindering Algorithm. More precisely, the operation interpolate satisfies exactly the specification of Algorithm 4. After the definition of the ChineseRemaindering domain we prove that its operation combine satisifies the specification of Algorithm 4 for the case of two moduli $m_1$ and $m_2$ . The reader is left with the proof of the operation interpolate which implements the general case (with $r \geq 2$ moduli).

ChineseRemaindering(E: EuclideanDomain): with {
        combine: 	(E, E) -> (E, E) -> E;
        interpolate: 	(List E, List E) -> E;
} == add {
        combine(m1: E, m2: E): (E, E) -> E == {
                local u1: E;
                assert(m1 = unitCanonical m1);
                assert(m2 = unitCanonical m2);
                fn(r1: E, r2: E): E == {
                        r1__new := r1 rem m1;
                        r := (r2 - r1__new) rem m2 ;
                        r :=  (r * u1) rem m2 ;
                        r := r1__new +  r * m1;
                }
                (u1, u2, g) := extendedEuclidean(m1, m2);
                fn
        }
        interpolate(lm: List E, lr: List E): E == {
                m := first lm;
                r := first lr rem m;
                for mi in rest lm for ri in rest lr repeat {
                        r := combine(m, mi)(r, ri);
                        m := m * mi;
                }
                return r;
        }
}

Proof. We need to prove that combine(m1,m2)(r1,r2) returns a qunatity congruent to that computed by Algorithm 4 modulo $m_1 \, m_2$ .

According to Algorithm 4 the case of two moduli $m_1$ and $m_2$ requires the following computations

• $r$ := 0
• $(u_1, v_1, g_1)$ := extendedEuclidean($m_1 \, m_2$ )
• $c_1$ := $r_1 v_1$ rem $m_1$
• $r$ := $r + c_1 m_2$
• $(u_2, v_2, g_2)$ := extendedEuclidean($m_2, m_1$ )
• $c_2$ := $r_2 v_2$ rem $m_2$
• $r$ := $r + c_2 m_1$

This can be simplified as follows:

• $(u_1, v_1, g_1)$ := extendedEuclidean($m_1 \, m_2$ )
• $c_1$ := $r_1 v_1$ rem $m_1$
• $c_2$ := $r_2 u_1$ rem $m_2$
• $r$ := $c_1 m_2 + c_2 m_1$

From the relations

$$\begin{array}{l} c_1 m_2 \equiv r_1 v_1 m_2 \mod{\, m_1 m_2},... ... \mod{\, m_1 m_2}, \\ u_1 m_1 + v_1 m_2 \ = \ 1, \\ \end{array}$$ (84)

we deduce the following congruences $\mod{\, m_1 m_2}$

$$\begin{array}{rcl} r & \equiv & c_1 m_2 + c_2 m_1 \\ & \equiv... ... u_1 m_1 \\ & \equiv & r_1 + (r_2 - r_1) u_1 m_1 \\ \end{array}$$ (85)

This last expression is exactly the quantity computed by combine(m1,m2)(r1,r2). This proves the implementation of the above operation combine. $\qedsymbol$