Cryptography Reference
In-Depth Information
Theorem 2.13
The CRT algorithm to solve the congruence system
⎫
⎬
x
≡
a
1
(
mod
m
1
)
x
≡
a
2
(
mod
m
2
)
(2.3)
.
⎭
x
≡
a
n
(
mod
m
n
)
where m
1
,
m
2
,...,
m
n
are pairwise relatively prime integers greater than 1 and
=
i
=
1
m
i
.
2
a
1
,
a
2
,...,
a
n
are integers, runs in time O
(
len
(
m
)
)
, where m
=
i
=
1
m
i
)(
i
=
1
len
Proof
Computing
m
requires time
O
(
len
(
m
(
m
i
))
=
2
2
O
(
len
(
m
)
)
. The computation of all the
M
i
requires time
O
(
len
(
m
)
)
as well. Com-
puting the
y
i
∈ Z
,1
≤
i
≤
n
, such that
y
i
M
i
≡
1
(
mod
m
i
)
requires, by Theorem
(
i
=
1
len
((
i
=
1
len
2
2.7 time
O
(
m
i
)
len
(
M
i
))
=
O
(
m
i
))
len
(
m
))
=
O
(
len
(
m
)
)
.
=
(
i
=
1
a
i
y
i
M
i
)
Finally, the computation of
x
mod
m
also requires time
2
2
O
(
len
(
m
)
)
, so the total time estimate is
O
(
len
(
m
)
)
.
2.6.1 The Chinese Remainder Theorem and the Residue
Class Ring
The Chinese remainder theorem has a natural interpretation in terms of the residue
class ring
=
i
=
1
m
i
is the product of the pairwise relatively prime
moduli. First we define the
direct product
of a family of rings (note that the direct
product of a family of groups can be similarly defined):
Z
m
, where
m
n
i
Definition 2.22
Let
{
R
i
}
1
be a family of rings. The
direct product
of this family
is the ring
i
=
1
R
i
=
={
(
x
1
,
x
2
,...,
x
n
)
|
x
i
∈
R
i
}
with addition and multiplication
defined component-wise, i.e., given two tuples
(
x
1
,
x
2
,...,
x
n
)
and
(
y
1
,
y
2
,...,
y
n
)
,
their sum is
(
x
1
+
y
1
,...,
x
n
+
y
n
)
and their product
(
x
1
y
1
,...,
x
n
y
n
)
.
An alternative notation for the direct product is
R
1
×
R
2
× ··· ×
R
n
and, in
particular, the direct product of two rings
R
,
S
is commonly denoted by
R
×
S
.
Example 2.12
Consider the rings
Z
3
and
Z
4
. Then their direct product is the ring
Z
3
× Z
4
={
(
0
,
0
), (
0
,
1
),...,(
2
,
2
), (
2
,
3
)
}
, which has 12 elements (in general,
|
×
|=|
|×|
|
(
,
)
R
S
R
S
). Note that the identity of this ring is the element
1
1
.
Now, the Chinese remainder theorem can be reformulated as follows:
n
Theorem 2.14
(Chinese remainder isomorphism)
Let
{
m
i
}
i
=
1
be a family of pair-
=
i
=
1
m
i
. Then the map
wise relative prime integers and n
