Cryptography Reference
In-Depth Information
a
6
=
a
5
·
a
≡
1
·
a
≡
3 mod 11
a
7
=
a
5
a
2
a
2
·
≡
1
·
≡
9 mod 11
a
8
=
a
5
a
3
a
3
·
≡
1
·
≡
5 mod 11
a
9
=
a
5
a
4
a
4
·
≡
1
·
≡
4 mod 11
a
10
=
a
5
a
5
·
≡
1
·
1
≡
1 mod 11
a
11
=
a
10
·
a
≡
1
·
a
≡
3 mod 11
.
{
3
,
9
,
5
,
4
,
1
}
We see that from this point on, the powers of
a
run through the sequence
indefinitely. This cyclic behavior gives rise to following definition:
Definition 8.2.4
Cyclic Group
A group G which contains an element
α
with maximum order
ord
(
is said to be
cyclic
. Elements with maximum order
are called
primitive elements
or
generators
.
α
)=
|
G
|
of a group
G
with maximum order is called a generator since
every element
a
of
G
can be written as a power
An element
α
i
=
a
of this element for some
i
,
α
i.e.,
generates
the entire group. Let us verify these properties by considering the
following example.
α
Example 8.6.
We want to check whether
a
= 2 happens to be a primitive element of
Z
11
=
|
Z
11
|
= 10.
Let's look at all the elements that are generated by powers of the element
a
= 2:
{
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
10
}
. Note that the cardinality of the group is
a
6
a
= 2
≡
9 mod 11
a
2
= 4
a
7
≡
7 mod 11
a
3
= 8
a
8
≡
3 mod 11
a
4
a
9
≡
5 mod 11
≡
6 mod 11
a
5
a
10
≡
10 mod 11
≡
1 mod 11
From the last result it follows that
|
Z
11
|
ord(
a
)=10 =
.
|
Z
11
|
This implies that (i)
a
= 2 is a primitive element and (ii)
is cyclic.
We now want to verify whether the powers of
a
= 2 actually generate all elements
of the group
Z
11
. Let's look again at all the elements that are generated by powers
of two.
i
123456789 0
a
i
2485 097361
By looking at the bottom row, we see that that the powers 2
i
in fact generate all
Z
11
. We note that the order in which they are generated looks
quite arbitrary. This seemingly random relationship between the exponent
i
and the
elements of the group
