Cryptography Reference
In-Depth Information
ε
g
−→
Z
n
× Z
n
Z
n
2
g
x
y
n
mod
n
2
(
x
,
y
)
−→
is a group isomorphism.
Proof
We start by showing that
ε
g
is a group homomorphism. Given
(
x
1
,
y
1
),
y
2
)
∈ Z
n
× Z
n
we have to show that
(
x
2
,
g
(
x
1
+
x
2
)
mod
n
n
mod
n
2
g
x
1
y
1
)(
g
x
2
y
2
)
mod
n
2
(
)
·
(
y
1
y
2
mod
n
)
=
(
.
Note first that, since the order of
g
is
n
, we have that
g
(
x
1
+
x
2
)
mod
n
mod
n
2
=
g
x
1
g
x
2
mod
n
2
. Thus it suffices to show that
n
mod
n
2
(
y
1
y
2
mod
n
)
=
n
mod
n
2
. Setting
r
(
y
1
y
2
)
=
=
+
y
1
y
2
mod
n
, we have that
y
1
y
2
nq
r
for some
i
=
0
i
(
n
i
r
n
−
i
. All the terms in
(
y
1
y
2
)
=
)
non-negative integer
q
and hence
nq
0 are multiples of
n
2
, so we obtain that
this sum except the one corresponding to
i
=
n
mod
n
2
r
n
mod
n
2
and
(
y
1
y
2
)
=
ε
g
is indeed a homomorphism.
ε
g
is an isomorphism, i.e., that it is bijective, observe first that
|Z
n
×Z
n
|=|Z
n
|·|Z
n
|=
Next, to prove that
p
2
q
2
n
2
n
·
φ(
n
)
=
p
(
p
−
1
)
q
(
q
−
1
)
=
φ(
)
·
φ(
)
=
φ(
)
,so
that both groups have the same order and hence it suffices to show that
ε
g
is injective.
Since
ε
g
is a group homomorphism, it is enough to show that its kernel is the trivial
group, i.e., that if
ε
g
(
,
)
=
(
,
)
=
(
,
)
∈ Z
n
and
x
y
1, then
x
y
0
1
. Assume then that
x
∈ Z
n
are such that
g
x
y
n
mod
n
2
1. This means that
g
x
mod
n
2
ε
g
(
,
)
=
=
y
x
y
and
y
n
mod
n
2
are mutually inverse in
Z
n
2
and hence it follows that they have the
same order. Since
g
has order
n
by hypothesis, the order of
g
x
mod
n
2
is a divisor
of
n
by Proposition 2.5 and, since
y
n
)
φ(
n
)
mod
n
2
1byCorollary2.1wehave,
by Proposition 2.4, that the order of
y
n
mod
n
2
is a divisor of
(
=
φ(
n
)
. Thus the order
of both elements is a divisor of both
n
and
1
as a consequence of
p
and
q
having the same length, we see that this order is equal
to 1 and hence
g
x
mod
n
2
φ(
n
)
and, since clearly gcd
(
n
,φ(
n
))
=
1 and
y
n
mod
n
2
=
=
1. The first equality means that
Z
n
2
, and
x
=
0 (since
g
has order
n
) and the second implies that the order of
y
in
Z
n
, is a divisor of
n
. Thus this order divides both
n
and
hence also the order of
y
in
φ(
n
)
and hence is equal to 1, so that we obtain
y
=
1, completing the proof.
Remark 8.9
Note that the hypothesis that the primes
p
,
q
have the same length has
only been used to ensure that gcd
(
n
,φ(
n
))
=
1 so that the former condition may be
replaced by the latter if desired.
Exercise 8.42
In [152, Lemma 1] it is shown that
ε
g
is bijective under the more
general assumption that the order of
g
is a nonzero multiple of
n
. Give an example
that shows that in this case
ε
g
is not necessarily a homomorphism.
Corollary 8.1
Given the same hypotheses as in the preceding proposition, let
π
:
Z
n
× Z
n
→ Z
n
be the canonical projection. Then the composition map
δ
g
=
π
◦
(ε
g
)
−
1
: Z
n
2
→ Z
n
is a group homomorphism.
