Cryptography Reference
In-Depth Information
Next we give a couple of elementary properties of the order of an element.
. Then x
t
Proposition 2.4
Let G be a group, x
∈
G and t
∈ Z
=
1
if and only if the
order of x divides t .
then
x
t
x
ik
x
i
k
Proof
If
i
is the order of
x
and
t
=
ik
for some
k
∈ Z
=
=
(
)
=
1
k
1. Conversely, if
x
t
=
=
1 and
i
is the order of
x
, performing the division of
t
by
x
t
x
iq
x
r
x
r
and, since
i
is,
i
we obtain
t
=
iq
+
r
with 0
≤
r
<
i
. Then 1
=
=
=
by definition, the smallest positive integer such that
x
i
=
1, we have that
r
=
0, so
that
t
=
iq
.
The order of a power may be computed as follows:
Proposition 2.5
Let G a group, x
∈
G an element of order i and k an integer. Then
x
k
has order i
/
gcd
(
i
,
k
)
.
x
k
i
/
gcd
(
i
,
k
)
x
i
k
/
gcd
(
i
,
k
)
Proof
Observe that
(
)
=
(
)
=
1. Thus, to prove that
is the order of
x
k
i
/
gcd
(
i
,
k
)
it suffices to show that it divides any integer
n
such
x
k
n
x
k
n
x
kn
that
(
)
=
1. But if
(
)
=
=
1 we see, by the preceding proposition, that
i
divides
kn
. This in turn implies that
i
/
gcd
(
i
,
k
)
divides
n
and we are done.
Next we show how to test whether a given integer
n
is the order of an element
x
G
where
G
is a group. This will also be useful in finding a generator of
G
in case
G
is cyclic, when one applies this to
n
∈
=|
G
|
, but observe that it requires knowledge
of the prime factors of
n
:
Proposition 2.6
Let n be a positive integer, G a group and x
∈
G. Then n is the
order of x in G if and only if x
n
1
and x
n
/
p
=
=
1
for each prime divisor p of n.
If
n
is the order of
x
then
n
is the smallest positive integer such that
x
n
Proof
=
1
and hence
x
n
/
p
1 holds for all prime divisors
p
of
n
. Conversely, assume that
these conditions hold. Since
x
n
=
1 we know from Proposition 2.4 that the order of
x
divides
n
. If the order is different from
n
then it divides some
n
=
p
and so
x
n
/
p
/
=
1,
a contradiction. Thus
n
is the order of
x
.
If
H
is a subgroup of a group
G
, then
H
defines an
equivalence relation
on
G
, namely, a relation which is
reflexive
,
symmetric
, and
transitive
, as follows. Given
x
∼
H
y
if
xy
−
1
,
y
∈
G
we say that
x
∈
H
. Then the relation
∼
H
is reflexive because
xx
−
1
H
and symmetric because if
xy
−
1
H
then
yx
−
1
xy
−
1
)
−
1
=
1
∈
∈
=
(
∈
H
. Transitivity is also clear because if
xy
−
1
H
and
yz
−
1
H
then
xz
−
1
∈
∈
=
xy
−
1
yz
−
1
∈
∈
H
.The
equivalence class
of
x
G
, i.e., the set of all elements which
={
|
∈
}
are related to
x
is
Hx
and, in this case, these sets are called the
right cosets
of
H
in
G
. Since any equivalence relation on a nonempty set defines
a partition of the set, namely, a decomposition of the set as a disjoint union of the
equivalence classes, we have that
G
is the disjoint union of all the right cosets (this
is also easy to prove directly but, for those not familiar with equivalence relations
and quotient sets, we refer to [45] or [48]).
hx
h
H
