Cryptography Reference
In-Depth Information
Definition 3.7 (Semigroup)
A
semigroup
is an algebraic structure
S,
∗
that con-
sists of a nonempty set
S
and an associative binary operation
∗
. The semigroup must
be closed (i.e., for all
a, b
∈
S
,
a
∗
b
must also be an element of
S
).
Note that this definition does not require a semigroup to have an identity
element. For example, the set of even integers (i.e.,
{
...,
−
4
,
−
2
,
0
,
2
,
4
,...
}
) with
the multiplication operation is a semigroup without identity element.
5
3.1.2.2
Monoids
As suggested in Definition 3.8, a monoid is a semigroup with the additional property
(or requirement) that it must have an identity element.
Definition 3.8 (Monoid)
A
monoid
is a semigroup
S,
∗
that has an identity ele-
ment
e
∈
S
with respect to
∗
.
are monoids with the identity
element 1. Also, the set of even integers with the addition operation and the identity
element 0, as well as the set of all binary sequences of nonnegative and finite length
with the string concatenation operation and the empty string representing the identity
element, are monoids. If the empty string is excluded from the set in the second case,
then the resulting algebraic structure is only a semigroup.
For example,
N
,
·
,
Z
,
·
,
Q
,
·
,and
R
,
·
3.1.2.3
Groups
As suggested in Definition 3.9, a group is a monoid in which every element is
invertible (and has an inverse element accordingly).
Definition 3.9 (Group)
A
group
is a monoid
S,
∗
in which every element
a
∈
S
has an inverse element in
S
(i.e., every element
a
∈
S
is invertible).
is associative, one can easily
show that the inverse element of an element must be unique (i.e., every element has
exactly one inverse element). Assume that
b
and
c
are both inverse elements of
a
.It
then follows that
b
=
b
Because
S,
∗
is a group and the operation
∗
∗
e
=
b
∗
(
a
∗
c
)=(
b
∗
a
)
∗
c
=
e
∗
c
=
c
, and hence the two
inverse elements of
a
must be the same.
Considering everything said so far, a group can also be defined as an algebraic
structure
S,
∗
that satisfies the following four axioms:
1.
Closure axiom:
∀
a, b
∈
S
:
a
∗
b
∈
S
;
5
The identity element with respect to multiplication would be 1 (which is not even).
