Cryptography Reference
In-Depth Information
f
−→
Z
m
Z
m
1
×···×Z
m
n
x
−→
(
x
mod
m
1
,
x
mod
m
2
,...,
x
mod
m
n
)
is a ring isomorphism. Moreover, this map induces by restriction an isomorphism
between the unit groups of these rings, namely an isomorphism
f
−→ Z
m
1
×···×Z
m
n
.
Z
m
Proof
It is clear that
f
is awell-defined function. It is also easy to show that
f
is a ring
homomorphism. For example, if
x
,
∈ Z
m
we have that
((
+
)
)
=
y
x
y
mod
m
mod
m
i
(
mod
m
i
and a similar formula holds for
the product. Now, in order to prove that
f
is bijective it suffices to show, for example,
that
f
is surjective because both its domain and its codomain have the same number
of elements. But, given an element
x
+
y
)
mod
m
i
=
(
x
mod
m
i
+
y
mod
m
i
)
x
n
)
∈ Z
m
1
×···×Z
m
n
, the Chinese
remainder theorem (Theorem 2.12) implies that the system of congruences
(
x
1
,
x
2
,...,
⎫
⎬
⎭
x
≡
x
1
(
mod
m
1
)
x
≡
x
2
(
mod
m
2
)
(2.4)
.
x
≡
x
n
(
mod
m
n
)
=
i
=
1
m
i
and this gives an element of
has a solution which is unique modulo
m
Z
m
whose image is
(actually, the CRT gives also the injectivity of
f
because the uniqueness of this solution shows that the element of
(
x
1
,
x
2
,...,
x
n
)
Z
m
that maps to
the given element of the product ring is unique).
For the final part observe that a ring isomorphism such as
f
has the property that
is a unit if and only if so is
x
. Indeed, if
x
is a unit with inverse
x
−
1
, then
(
)
f
x
xx
−
1
x
−
1
is also a unit and the converse
follows in a similar way using the inverse isomorphism. Thus the last claim in the
statement of the theorem follows bearing in mind that the unit group of the product
ring is
f
(
)
=
f
(
1
)
=
1
=
f
(
x
)
f
(
)
, so that
f
(
x
)
Z
m
1
×···×Z
m
n
as it is clear that an element in the product ring is a unit if
and only if each of its components is a unit in the corresponding factor ring.
Exercise 2.15
Show that Theorems 2.12 and 2.14 are equivalent in the sense that
not only is the latter a corollary of the former as we have seen but also the former
can be deduced from the latter.
Exercise 2.16
Show that the ring
Z
4
is not isomorphic to the product
Z
2
× Z
2
and
that their unit groups are not isomorphic either.
As we will see later, one interesting application of the CRT is the speed-up of RSA
decryption. Another interesting application is in multiprecision arithmetic and in the
construction of the so-called
residue computers
that use the CRT to subdivide large
computations in
Z
i
=
1
m
i
Z
m
i
. This can
provide a considerable efficiency gain because, on the one hand, the computations in
into several computations in the smaller rings
