next up previous
Next: Modular computation of the determinant Up: Modular Algorithms and interpolation Previous: Evaluation, interpolation

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

($\displaystyle \forall$x $\displaystyle \in$ $\displaystyle \mbox{${\mathbb Z}$}$)     $\displaystyle \left\{\vphantom{ \begin{array}{l} x \equiv a \mod{\, m} \\  x \equiv b \mod{\, n} \\  \end{array} }\right.$$\displaystyle \begin{array}{l} x \equiv a \mod{\, m} \\  x \equiv b \mod{\, n} \\  \end{array}$  $\displaystyle \iff$  x $\displaystyle \equiv$ c mod m n (36)

where a convenient c is given by

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

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

$\displaystyle \left\{\vphantom{ \begin{array}{l} x \equiv a \mod{\, m} \\  x \equiv b \mod{\, n} \\  \end{array} }\right.$$\displaystyle \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

c $\displaystyle \equiv$ a mod m        and        c $\displaystyle \equiv$ b mod n. (39)

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

x $\displaystyle \equiv$ c mod m        and        x $\displaystyle \equiv$ c mod n (40)

Thus Relations (39) and (40) lead to

x $\displaystyle \equiv$ a mod m        and        x $\displaystyle \equiv$ b mod n (41)

Conversly 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 I0, I1,..., In-1 be ideals of R. We consider the direct product of residue class rings R/I0× ... ×R/In-1 (additions and multiplications are computed componentwise) together with the homomorphism

M : $\displaystyle \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

Proof. The first statement is obvious. Let us prove the second one. Let r, r0, r1,..., rn-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

M(r) = ($\displaystyle \overline{{r_0}}^{{{I_0}}}_{{}}$,...,$\displaystyle \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$) (44)

that is

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

or

$\displaystyle \overline{{r - r_0}}^{{{I_0}}}_{{}}$  =  $\displaystyle \overline{{r - r_1}}^{{{I_1}}}_{{}}$  =   ...   =  $\displaystyle \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

$\displaystyle \overline{{a}}^{{{I+J}}}_{{}}$ = $\displaystyle \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

{x $\displaystyle \in$ R  |  a - x $\displaystyle \in$ I}  =  {x $\displaystyle \in$ R  |  b - x $\displaystyle \in$ J} (48)

or equivalently

{x $\displaystyle \in$ R  |  ($\displaystyle \exists$u $\displaystyle \in$ I)  |  x = a + u}  =  {x $\displaystyle \in$ R  |  ($\displaystyle \exists$v $\displaystyle \in$ I)  |  x = b + v} (49)

Since these sets are non empty this implies

($\displaystyle \exists$(u, v) $\displaystyle \in$ I×J)  |  a + u = b + v. (50)

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

a - b $\displaystyle \in$ I + J (51)

The lemma is proved. $ \qedsymbol$

CONTINUING THEOREM'S

Proof. With the previous lemma Relation 46 leads to

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

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

$\displaystyle \overline{{r_i}}^{{{I_i + I_j}}}_{{}}$ = $\displaystyle \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

$\displaystyle \overline{{r}}^{{{I_i}}}_{{}}$  =  $\displaystyle \overline{{1}}^{{{I_i}}}_{{}}$    and    $\displaystyle \overline{{r}}^{{{I_j}}}_{{}}$  =  $\displaystyle \overline{{0}}^{{{I_j}}}_{{}}$ (54)

Hence

1 - r $\displaystyle \in$ Ii    and    r $\displaystyle \in$ Ij (55)

which implies Ii + Ij = 1. Conversly, let us assume that the ideals I0,..., In-1 are pairwise coprime. Let i be in the range 0 ... n - 1 and consider the product I of all ideals I0,..., In-1 except Ii. It is a classical result that Ii and I are coprime. Let ui $ \in$ Ii and vi $ \in$ I such that ui + vi = 1. Observe that for j = 0 ... n - 1

$\displaystyle \overline{{v_i}}^{{{I_i}}}_{{}}$  =  $\displaystyle \overline{{1}}^{{{I_i}}}_{{}}$    and    j $\displaystyle \neq$ i  $\displaystyle \Longrightarrow$ $\displaystyle \overline{{v_i}}^{{{I_j}}}_{{}}$  =  $\displaystyle \overline{{0}}^{{{I_j}}}_{{}}$. (56)

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

r  =  v0r0 + ... + vn-1rn-1 (57)

satisfies

M(r)  =  ($\displaystyle \overline{{r_0}}^{{{I_0}}}_{{}}$,...,$\displaystyle \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 I0,..., In-1 be ideals of R such that we have Ii + Ij = R for every i, j with 0 $ \leq$ i < j $ \leq$ n - 1. Let I be the product of the ideals I0,..., In-1. Then we have the ring isomorphism

R/I  $\displaystyle \simeq$  R/I0× ... ×R/In-1 (59)

and the group isomorphism of the multiplicative groups

(R/I) *   $\displaystyle \simeq$  (R/I0) * × ... ×(R/In-1) * (60)

Proof. The following ring isomorphism follows from Theorem 3

R/( $\displaystyle \cap_{{{0 \leq i \leq n-1}}}^{{}}$ Ii$\displaystyle \simeq$  R/I0× ... ×R/In-1 (61)

It is a well known fact that if the ideals I0,..., In-1 are pairwise coprime ( Ii + Ij = 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

($\displaystyle \overline{{r_0}}^{{{I_0}}}_{{}}$,...,$\displaystyle \overline{{r_{n-1}}}^{{{I_{n-1}}}}_{{}}$$\displaystyle \in$  R/I0× ... ×R/In-1 (62)

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

From now on R denotes an Euclidean domain.

Corollary 2   Let m0,..., mn-1 be n elements pairwise coprime in the Euclidean domain R. (Hence for 0 $ \leq$ i < j < n we have gcd(mi, mj) = 1.) Then let m = m0 ... mr-1. We have the ring isomorphism

R/m  $\displaystyle \simeq$  R/m0× ... ×R/mn-1 (63)

and the group isomorphism of the multiplicative groups

(R/m) *   $\displaystyle \simeq$  (R/m0) * × ... ×(R/mn-1) * (64)

Proof. These are well known facts in an Euclidean domain R. Then the ring isomorphism and the groups isomorphism follow from Corollary 1 by considering the ideals I0 = $ \langle$m0$ \rangle$, ... In-1 = $ \langle$mn-1$ \rangle$. $ \qedsymbol$

Algorithm 4  

\fbox{
\begin{minipage}{12 cm}
\begin{description}
\item[{\bf Input:}] $m_0, \do...
... := $r + c_i \frac{m}{m_i}$\ \\
\> {\bf return} $r$\end{tabbing}\end{minipage}}

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

ui mi + vi$\displaystyle {\frac{{m}}{{m_i}}}$  =  1 (65)

Hence

rivi$\displaystyle {\frac{{m}}{{m_i}}}$    $\displaystyle \equiv$    rimod mi (66)

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

rivi$\displaystyle {\frac{{m}}{{m_i}}}$    $\displaystyle \equiv$    0 mod mj (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

r $\displaystyle \equiv$ rimod mi  for i = 0 ... n - 1 (68)

Any other solution r' of (68) satisfies r $ \equiv$ r'mod m where m is the product of the moduli m0,..., mr-1. This follows from the fact the mi's are pairwise coprime and from Corollary 2. Therefore the set all solutions of (68) is of the form

{r + k m  |  k $\displaystyle \in$ R} (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 m0,..., mr-1 $ \in$ R be polynomials pairwise coprime ( gcd(mi, mj) = 1 for 0 $ \leq$ i < j $ \leq$ r - 1). Let m be their product. For 0 $ \leq$ i $ \leq$ r - 1 let di $ \geq$ 1 be the degree of mi and n = $ \Sigma_{{{i=0}}}^{{{r-1}}}$di be the degree of m. For 0 $ \leq$ i $ \leq$ r - 1 let fi $ \in$ $ \bf k$[x] be a polynomial with degree deg(fi) < di. Then there is a unique polynomial f $ \in$ $ \bf k$[x] such that

deg(f ) < n    and    f $\displaystyle \equiv$ fimod mi  for  i = 0 ... r - 1. (71)

Moreover it can be computed in $ \cal {O}$(n2) 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

f $\displaystyle \equiv$ g mod mi  for  i = 0 ... r - 1. (72)

and thus

f $\displaystyle \equiv$ g mod m (73)

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

Theorem 5   Let m0,..., mr-1, m be in R = $ \mbox{${\mathbb Z}$}$ such that the mi's are pairwise coprime and m is their product. Let n be the word length of m. Let a0,..., ar-1 $ \in$ R be such that 0 $ \leq$ ai < mi for i = 0 ... r - 1. Then there is a unique a $ \in$ R such that

0 $\displaystyle \leq$ a < m    and    a $\displaystyle \equiv$ aimod mi  for  i = 0 ... r - 1. (74)

Moreover it can be computed in $ \cal {O}$(n2) 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 m1 and m2. 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 m1 m2.

According to Algorithm 4 the case of two moduli m1 and m2 requires the following computations

This can be simplified as follows: From the relations

c1m2 $\displaystyle \equiv$ r1v1m2mod m1m2,
c2m1 $\displaystyle \equiv$ r2u1m1mod m1m2,
u1m1 + v1m2  =  1,
(75)

we deduce the following congruences mod m1m2

r $\displaystyle \equiv$ c1m2 + c2m1
  $\displaystyle \equiv$ r1v1m2 + r2u1m1
  $\displaystyle \equiv$ r1(1 - u1m1) + r2u1m1
  $\displaystyle \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$


next up previous
Next: Modular computation of the determinant Up: Modular Algorithms and interpolation Previous: Evaluation, interpolation
Marc Moreno Maza
2003-06-06