Cryptography Reference
In-Depth Information
2.6 The Chinese Remainder Theorem
The Chinese remainder theorem is a clever method to solve systems of linear con-
gruences that goes back to the Chinese mathematician Sun Tsu (or Sun Zi) who
lived sometime between 200
. It is said [162] that it was used by the
Chinese generals to count the number of soldiers by lining them in multiples of 7,
10, etc. and counting the remaining soldiers in each case. In his classic three-volume
topic
Mathematics Manual
, Sun Tsu proposed the following problem: find a number
that leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5,
and a remainder of 2 when divided by 7. This amounts to finding a positive integer
satisfying the following system of congruences:
BC
and 200
AD
⎫
⎬
≡
(
)
x
2
mod 3
≡
(
)
x
3
mod 5
(2.1)
⎭
x
≡
2
(
mod 7
)
The general version of the theorem about these systems is as follows:
Theorem 2.12
(Chinese remainder theorem, CRT)
Let m
1
,
m
2
,...,
m
n
be pairwise
relatively prime integers greater than 1 and let a
1
,
a
2
,...,
a
n
be integers. Then the
system of congruences
⎫
⎬
x
≡
a
1
(
mod
m
1
)
x
≡
a
2
(
mod
m
2
)
(2.2)
.
⎭
x
≡
a
n
(
mod
m
n
)
=
i
=
1
m
i
.
has a solution which is unique modulo m
=
j
=
i
m
j
. Since the
m
i
are pairwise
Proof
For each
i
=
1
,...,
n
,let
M
i
=
m
/
m
i
relatively prime we have that gcd
(
m
i
,
M
i
)
=
1 for each
i
such that 1
≤
i
≤
n
. Thus
each
M
i
is invertible in
Z
m
i
by Theorem 2.11 and, using the extended Euclidean
algorithm, we may compute integers
y
i
∈ Z
such that for each 1
≤
i
≤
n
,
y
i
M
i
≡
1
(
mod
m
i
)
=
(
i
=
1
a
i
y
i
M
i
)
Then we set
x
mod
m
and we claim that
x
is the unique solution
of the system (
2.2
) modulo
m
. Indeed, we observe that
y
i
M
i
≡
1
(
mod
m
i
)
implies
a
i
y
i
M
i
≡
a
i
(
mod
m
i
)
for 1
≤
i
≤
n
and, since
m
i
|
M
j
for each
j
=
i
, we obtain:
a
j
y
j
M
j
≡
0
(
mod
m
i
)
for 1
j
. We see that
a
i
y
i
M
i
is a solution of the
i
th congruence and
does not contribute to the remaining ones, so the sum of all these terms satisfies
≤
i
,
j
≤
n
,
i
=
