Cryptography Reference
In-Depth Information
Definition 3.3 (Left identity element)
Let
S
be a set and
∗
a binary operation on
S
.Anelement
e
∈
S
is called
left identity element
if
e
∗
a
=
a
for all
a
∈
S
.
Definition 3.4 (Right identity element)
Let
S
be a set and
∗
a binary operation on
S
.Anelement
e
∈
S
is called
right identity element
if
a
∗
e
=
a
for all
a
∈
S
.
Definition 3.5 (Identity element)
Let
S
be a set and
∗
a binary operation on
S
.
An element
e
S
is called
identity element
(or
neutral element
)ifitisbothaleft
identity element and a right identity element (i.e.,
e
∈
∗
a
=
a
∗
e
=
a
for all
a
∈
S
).
Note that an identity element does not have to exist, but if it exists it must
be unique. This can easily be shown by assuming that
e
1
and
e
2
are both identity
elements. It then follows from the definition of an identity element that
e
1
=
e
1
∗
e
2
=
e
2
, and hence
e
1
=
e
2
. Also note that we don't require the operation
∗
to be commutative. For example, the identity matrix is the identity element of the
matrix multiplication, and this operation is not commutative.
If there exists an identity element
e
, then some elements
of
S
may also have inverse elements. This is captured in Definition 3.6.
∈
S
with respect to
∗
Definition 3.6 (Inverse element)
Let
S
be a set,
be a binary operation with an
identity element
e
, and
a
be an element of
S
. If there exists an element
b
∗
∈
S
with
a
∗
b
=
b
∗
a
=
e
,then
a
is
invertible
and
b
is the
inverse element
(or
inverse
)of
a
.
Note that not all elements in a given set must be invertible and have inverse
elements with respect to the operation under consideration. As discussed below, the
question whether all elements are invertible is the distinguishing feature between a
group and a monoid or between a field and a ring, respectively.
3.1.2
Algebraic Sructures
An
algebraic structure
4
consists of a nonempty set
S
and one or more binary
operations. For the sake of simplicity, we sometimes omit the operation(s) and use
S
to denote the entire structure. In this section, we overview and briefly discuss the
algebraic structures that are most frequently used in algebra. Among these structures,
groups, rings, and (finite) fields are particularly important for cryptography in
general, and public key cryptography in particular.
3.1.2.1
Semigroups
The simplest algebraic structure is a semigroup as formally introduced in Definition
3.7.
4
In some literature, an algebraic structure is also called
algebra
or
algebraic system
.
