Cryptography Reference
In-Depth Information
n
x
≡
a
i
y
i
M
i
+
a
j
y
j
M
j
≡
a
i
(
mod
m
i
)
j
=
1
j
=
i
for 1
n
. This proves the existence and, for the uniqueness, let us note that if
x
is another solution of the system, then
x
≤
i
≤
x
≡
(
mod
m
i
)
and, since the
m
i
are
x
(
pairwise relatively prime, this clearly implies
x
≡
mod
m
)
.
Example 2.11
Let us consider Sun Tsu's problem (Eq. (
2.1
)). We compute:
=
·
·
=
,
m
3
5
7
105
M
−
1
1
35
−
1
mod 3
M
1
=
m
/
m
1
=
105
/
3
=
35
,
y
1
=
mod
m
1
=
=
2
;
M
−
1
2
21
−
1
mod 5
M
2
=
m
/
m
2
=
105
/
5
=
21
,
y
2
=
mod
m
2
=
=
1
;
M
−
1
3
15
−
1
mod 7
M
3
=
m
/
m
3
=
105
/
7
=
15
,
y
3
=
mod
m
3
=
=
1
.
Thus we obtain the solution:
3
mod
m
x
=
a
i
y
i
M
i
=
(
2
·
2
·
35
+
3
·
1
·
21
+
2
·
1
·
15
)
mod 105
=
23
.
i
=
1
Of course, this can be also done with Maple, which has the CRT algorithm imple-
mented in the function
chrem
. To solve Sun Tsu's problem we simply compute:
> chrem([2, 3, 2], [3, 5, 7]);
23
Remarks 2.2
1. An important feature of the proof of the CRT given above is that it is constructive
and it actually gives an algorithm for computing the solution(s).
2. The
y
i
and the
M
i
defined in the proof of Theorem 2.12 do not depend on the
a
i
(they depend only on the
m
i
). This is often useful in applications where the
m
i
are fixed, for then the
y
i
and the
M
i
can be pre-computed and one only has to
substitute the
a
i
in the formula
x
=
(
i
=
1
a
i
y
i
M
i
)
mod
m
to obtain the solution
in a faster way.
3. The modern interpretation of the CRT places the theorem in the setting of com-
mutative ring theory as we will see in Theorem 2.14 below.
The complexity of the algorithm for the CRT given in the proof of Theorem 2.12
can be estimated as follows:
