Cryptography Reference
In-Depth Information
a
∗
a
a
∗
a
∗
a
...
a
∗
a
∗
...
∗
a
n
times
are different and represent all elements of
S
, then the group
is called
cyclic
and
a
is called a
generator
of the group (or a
primitive root
of the group's identity
element, respectively). If
a
generates the group (in the sense that
a
is a generator
of the group), then we may write
S
=
S,
∗
. If a finite group is cyclic, then there are
typically many generators. In fact, there are
φ
(
n
a
−
1) generators if
n
refers to the
order of the group.
7
For example,
Z
n
,
+
is a cyclic group with generator 1. This basically means
that every number of
{
0
,
1
,
2
,
3
,...,n
−
1
}
can be generated by adding 1 modulo
n
a certain number of times:
0
=
1+1+
...
+1
n
times
1=1
2=1+1
3
=
1+1+1
...
n
−
1
=
1+1+
...
+1
n
−
1times
Z
7
,
As illustrated in Figure 3.2,
·
is a cyclic group with generator 3 (i.e.,
Z
7
,
Z
7
·
=
3
). This means that every element of
=
{
1
,
2
,...,
6
}
can be
Z
7
.
In either case, it is important to note that not all finite groups must be cyclic
(and hence not all finite groups must have a generator), but that all cyclic groups
must be Abelian. The converse of the second fact is not true, meaning that an Abelian
group must not necessarily be cyclic.
represented by 3 to the power of another element of
7
The function
φ
is called Euler's totient function and is formally introduced in Section 3.2.6.
