Cryptography Reference
In-Depth Information
Proving converse result is a bit more technical. We assume that
n
is such that
p
α
1
×···×
b
n
−
1
p
α
r
r
be the factorization of
n
where the
p
i
's are pairwise different prime numbers. We use two lemmata.
Z
n
. Let
n
≡
1
(mod
n
) for any
b
∈
=
Lemma 7.2.
Let G be a group of order n. If p is a prime factor of n, there exists an
element of order p in G.
Lemma 7.3.
Given a finite group G, we call
exponent
of G the smallest integer
µ
such
that x
µ
=
1
for all x
∈
G. The exponent is equal to the lcm of all element orders in G.
If n is such that x
n
=
1
for all x
∈
G, then
µ
must be a factor of n.
From this we infer that the exponent and the group order have exactly the same prime
factors. In our case,
G
is
Z
n
(whose order is
ϕ
(
n
)) and
b
n
−
1
≡
1
(mod
n
) for all
b
∈
G
, and thus all prime factors of
ϕ
(
n
) are factors of
n
−
1. If for some
i
we had
α
i
>
1, then
p
i
would be a factor of
ϕ
(
n
), and therefore a factor of
n
−
1 as well. But
a
p
i
cannot simultaneously be a factor of
n
and
n
−
1. Therefore we have that
α
i
=
1
for all
i
.
We know from the Chinese Remainder Theorem that
Z
n
is isomorphic to
Z
p
1
Z
p
r
. Since
Z
p
i
×···×
is a cyclic subgroup of order
p
i
−
1, there must be an element
b
of order
p
i
−
1, but
b
n
−
1
≡
1 (mod
n
) implies that
p
i
−
−
1 is a factor of
n
1 for
any
i
.
Proof (Lemma 7.2).
We prove this by induction on the order of
G
. This is trivial when
the order is 1. If
x
is an element of
G
of order
k
1, we first assume that
p
is not a
factor of
k
.
x
generates a subgroup
H
of
G
of order
k
, and
G
>
/
H
is a group of order
n
k
n
. Since this is a factor of
p
, there must be an element
yH
of order
p
. It is then
easy to see that the order of
y
must be a multiple of
p
. This shows that we must have
an element
x
of
G
of order multiple of
p
. It is then easy to see that
x
p
is of order
p
.
<
for which
x
µ
=
Proof (Lemma 7.3).
Let
H
be the set of all integers
G
.
It is quite easy to notice that
H
is a subgroup of
Z
: it is not empty (it contains the
order of
G
), it is stable with respect to addition and subtraction. Due to a structure
property
1
µ
1 for all
x
∈
of
Z
,
H
must be generated by a single integer
µ
which is the exponent of
G
.
We also prove by induction that we can compute the smallest integral power which
makes all elements of a subset
A
vanish by computing the lcm of the orders of all
elements in
A
.
1
When considering the smallest nonnegative element
µ
of
H
, we can prove that
µ
spans the whole subgroup
H
: clearly, all elements spanned by
µ
are in
H
; conversely, if
x
∈
H
, the Euclidean division
x
=
q
µ
+
r
of
x
by
µ
tells us that
r
=
x
−
q
µ
is in
H
as well and 0
≤
r
<µ
, but since
µ
is the smallest nonnegative
element of
H
, then we must have
r
=
0, which means that
x
=
q
µ
is spanned by
µ
.
Search WWH ::
Custom Search