The Chinese Remaindering Algorithm

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

Theorem 2 (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 \in \mbox{${\mathbb Z}$} \left\{\vphantom{ \begin{array}{l} x \equiv a \mod{\, m} \\ x \equiv b \mod{\, n} \\ \end{array} }\right. \begin{array}{l} x \equiv a \mod{\, m} \\ x \equiv b \mod{\, n} \\ \end{array} \iff \equiv$$ (36)

where a convenient c is given by

c  =  a + (b - a) s m = b + (a - b)t n (37)

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

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

has a solution.

Proof. First observe that Relation (37) implies

$$\equiv \equiv$$ (39)

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

$$\equiv \equiv$$ (40)

Thus Relations (39) and (40) lead to

$$\equiv \equiv$$ (41)

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 3   Let R be a commutative ring with unity and I₀, I₁,..., I_n-1 be ideals of R. We consider the direct product of residue class rings R/I₀× ^... ×R/I_n-1 (additions and multiplications are computed componentwise) together with the homomorphism

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

Then we have

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

  $$\forall \leq \leq \Longrightarrow \overline{{r_i}}^{{{I_i + I_j}}}_{{}} \overline{{r_j}}^{{{I_i + I_j}}}_{{}}$$ (43)

  
  

• 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₀, r₁,..., r_n-1 be in R. We look for the pre-image of ($\overline{{r_0}}^{{{I_0}}}_{{}}$,...,$\overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$). Hence we look for r such that

$$\overline{{r_0}}^{{{I_0}}}_{{}} \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$$ (44)

that is

$$\overline{{r}}^{{{I_0}}}_{{}} \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}} \overline{{r_0}}^{{{I_0}}}_{{}} \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$$ (45)

or

$$\overline{{r - r_0}}^{{{I_0}}}_{{}} \overline{{r - r_1}}^{{{I_1}}}_{{}} \overline{{r - r_{n-1}}}^{{{I_{n-1}}}}_{{}}$$ (46)

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}}}_{{}}$$ (47)

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

$$\in \in \in \in$$ (48)

or equivalently

$$\in \exists \in \in \exists \in$$ (49)

Since these sets are non empty this implies

$$\exists \in$$ (50)

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

$$\in$$ (51)

The lemma is proved. $\qedsymbol$

CONTINUING THEOREM'S

Proof. With the previous lemma Relation 46 leads to

$$\overline{{r - r_i}}^{{{I_i + I_j}}}_{{}} \overline{{r - r_j}}^{{{I_i + I_j}}}_{{}}$$ (52)

for i, j such that 0 $\leq$ i < j $\leq$ n - 1 or equivalently

$$\overline{{r_i}}^{{{I_i + I_j}}}_{{}} \overline{{r_j}}^{{{I_i + I_j}}}_{{}}$$ (53)

Relation (53) 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}}}_{{}} \overline{{r}}^{{{I_j}}}_{{}} \overline{{0}}^{{{I_j}}}_{{}}$$ (54)

Hence

$$\in \in$$ (55)

which implies I_i + I_j = 1. Conversly, let us assume that the ideals I₀,..., I_n-1 are pairwise coprime. Let i be in the range 0 ^... n - 1 and consider the product I of all ideals I₀,..., 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 j = 0 ^... n - 1

$$\overline{{v_i}}^{{{I_i}}}_{{}} \overline{{1}}^{{{I_i}}}_{{}} \neq \Longrightarrow \overline{{v_i}}^{{{I_j}}}_{{}} \overline{{0}}^{{{I_j}}}_{{}}$$ (56)

Now consider ($\overline{{r_0}}^{{{I_0}}}_{{}}$,...,$\overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$) $\in$ R/I₀× ^... ×R/I_n-1. Then

r  =  v₀r₀ + ^... + v_n-1r_n-1 (57)

satisfies

$$\overline{{r_0}}^{{{I_0}}}_{{}} \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$$ (58)

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

Corollary 1   Let R be a commutative ring with unity and I₀,..., 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₀,..., I_n-1. Then we have the ring isomorphism

$$\simeq$$ (59)

and the group isomorphism of the multiplicative groups

$$\simeq$$ (60)

Proof. The following ring isomorphism follows from Theorem 3

$$\cap_{{{0 \leq i \leq n-1}}}^{{}} \simeq$$ (61)

It is a well known fact that if the ideals I₀,..., 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}}}_{{}} \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}} \in$$ (62)

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₀,..., m_n-1 be n elements pairwise coprime in the Euclidean domain R. (Hence for 0 $\leq$ i < j < n we have gcd(m_i, m_j) = 1.) Then let m = m₀ ^... m_r-1. We have the ring isomorphism

$$\simeq$$ (63)

and the group isomorphism of the multiplicative groups

$$\simeq$$ (64)

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₀ = $\langle$m₀$\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 ^... n - 1 we have

$${\frac{{m}}{{m_i}}}$$ (65)

Hence

$${\frac{{m}}{{m_i}}} \equiv$$ (66)

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

$${\frac{{m}}{{m_i}}} \equiv$$ (67)

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

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

$$\equiv$$ (68)

Any other solution r' of (68) satisfies r $\equiv$ r'mod m where m is the product of the moduli m₀,..., 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 (68) is of the form

$$\in$$ (69)

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

d (r)  <  d (m) (70)

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

Theorem 4   Let R = $\bf k$[x] for a field $\bf k$. Let m₀,..., 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

$$\equiv$$ (71)

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

Proof. Except for the complexity result (that can be found in [vzGG99] 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 (71). Then we have

$$\equiv$$ (72)

and thus

$$\equiv$$ (73)

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

Theorem 5   Let m₀,..., 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₀,..., a_r-1 $\in$ R be such that 0 $\leq$ a_i < m_i for i = 0 ^... r - 1. Then there is a unique a $\in$ R such that

$$\leq \equiv$$ (74)

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

Proof. Except for the complexity result (that can be found in [vzGG99] 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₁ and m₂. 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₁ m₂.

According to Algorithm 4 the case of two moduli m₁ and m₂ requires the following computations

• r := 0
• (u₁, v₁, g₁) := extendedEuclidean(m₁, m₂)
• c₁ := r₁v₁ rem m₁
• r := r + c₁m₂
• (u₂, v₂, g₂) := extendedEuclidean(m₂, m₁)
• c₂ := r₂v₂ rem m₂
• r := r + c₂m₁

This can be simplified as follows:

• (u₁, v₁, g₁) := extendedEuclidean(m₁, m₂)
• c₁ := r₁v₁ rem m₁
• c₂ := r₂u₁ rem m₂
• r := c₁m₂ + c₂m₁

From the relations

c1m2 $$\equiv$$ r1v1m2mod m1m2, c2m1 $$\equiv$$ r2u1m1mod m1m2, u1m1 + v1m2  =  1,

(75)

we deduce the following congruences mod m₁m₂

r	$$\equiv$$	c1m2 + c2m1
	$$\equiv$$	r1v1m2 + r2u1m1
	$$\equiv$$	r1(1 - u1m1) + r2u1m1
	$$\equiv$$	r1 + (r2 - r1)u1m1

(76)

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