Cryptography Reference
In-Depth Information
2.
Associativity axiom:
∀
a, b, c
∈
S
:
a
∗
(
b
∗
c
)=(
a
∗
b
)
∗
c
;
3.
Identity axiom:
∃
a unique identity element
e
∈
S
such that
∀
a
∈
S
:
a
∗
e
=
e
∗
a
=
a
;
a unique inverse element
a
−
1
4.
Inverse axiom:
∀
a
∈
S
:
∃
∈
S
such that
a
−
1
=
a
−
1
a
∗
∗
a
=
e
.
The operations most frequently used in groups are addition (+) and multi-
plication (
). Such groups are called
additive groups
and
multiplicative groups
.For
multiplicative groups, the symbol
·
b
is written as
ab
.For
additive and multiplicative groups, the identity elements are usually denoted as 0
and 1, whereas the inverse elements of element
a
are usually denoted as
·
is often omitted, and
a
·
a
and
a
−
1
.
Consequently, a multiplicative group is assumed in the fourth axiom given here.
−
Commutative Groups
A distinction is often made between commutative and noncommutative groups. The
notion of a commutative group is formally introduced in Definition 3.10.
Definition 3.10 (Commutative group)
A group
S,
∗
is
commutative
if the opera-
tion
∗
is commutative (i.e.,
a
∗
b
=
b
∗
a
for all
a, b
∈
S
).
In the literature, commutative groups are also called
Abelian
groups. If a
group is not commutative, then it is called
noncommutative
or
non-Abelian
.For
example,
Z
,
+
,
Q
,
+
,and
R
,
+
are commutative groups with the identity
element 0. The inverse element of
a
is
are
commutative groups with the identity element 1. In this case, the inverse element of
a
is
a
−
1
. Furthermore, the set of real-valued
n
−
a
. Similarly,
Q
\{
0
}
,
·
and
R
\{
0
}
,
·
n
matrices is a commutative group
with respect to matrix addition, whereas the subset of nonsingular (i.e., invertible)
matrices is a noncommutative group with respect to matrix multiplication.
×
Finite Groups
Groups can be finite or infinite (depending on the number of elements). Finite groups
as captured in Definition 3.11 play a fundamental role in (public key) cryptography.
Definition 3.11 (Finite group)
A group
S,
∗
is
finite
if it contains only finitely
many elements.
The order of a finite group
S,
∗
equals the cardinality of the set
S
(i.e.,
|
S
|
).
Hence, another way to define a finite group is to say that
.
For example, the set of permutations of
n
elements is finite and has
n
! elements.
S,
∗
is finite if
|
S
|
<
∞
