Cryptography Reference
In-Depth Information
It is a noncommutative group with respect to the composition of permutations (see
Section 3.1.4). More interestingly,
Z
n
,
are finite groups that have
many cryptographic applications. As explained later in this chapter,
Z
n
,
+
and
·
Z
n
consists of
Z
n
consists of all integers between 1 and
n
all integers from 0 to
n
−
1, whereas
−
1
that have no common divisor with
n
greater than 1.
6
If
S,
∗
is a group, then for any element
a
∈
S
and for any positive integer
,
a
i
i
∈
N
∈
S
denotes the following element in
S
:
a
∗
a
∗
...
∗
a
i
times
Due to the closure axiom (i.e., axiom 1), this element must again be in
S
.
Note that we use
a
i
only as a shorthand representation for the element, and that the
operation between the group element
a
and the integer
i
is not the group operation.
For additive groups,
a
i
is sometimes also written as
i
·
a
(or
ia
, respectively). But
note again that
i
·
a
only represents the resulting group element and that
·
is not the
group operation.
Cyclic Groups
If
S,
∗
is a finite group with identity element
e
(with respect to
∗
), then the order of
S
, denoted as
ord
(
a
), is the least positive integer
n
such that
a
ord
(
a
)
equals
e
. This can be formally expressed as follows:
an element
a
∈
a
∗
a
∗
...
∗
a
=
e.
ord
(
a
)times
Alternatively speaking, the order of an element
a
∈
S
(in a multiplicative
group) is defined as follows:
a
n
=
e
ord
(
a
):=
min
{
n
≥
1
|
}
If there exists an element
a
∈
S
such that the elements
a
Note that the star used in
Z
n
has nothing to do with the star used in Definition 3.11. In the second
case, the star represents an arbitrary binary operation.
6
