Cryptography Reference
In-Depth Information
Definition 4.3.1
Group
A
group
is a set of elements G together with an operation
◦
which
combines two elements of G. A group has the following properties:
1. The group operation
◦
is
closed
. That is, for all a
,
b
,
∈
G, it holds
G.
2. The group operation is
associative
. That is, a
that a
◦
b
=
c
∈
◦
(
b
◦
c
)=(
a
◦
b
)
◦
c
G.
3. There is an element
1
for all a
,
b
,
c
∈
∈
G, called the
neutral element
(or
identity
element
), such that a
◦
1 = 1
◦
a
=
a for all a
∈
G.
G there exists an element a
−
1
4. For each a
∈
∈
G, called the
in-
a
−
1
=
a
−
1
a
= 1
.
5. A group G is
abelian (or commutative)
if, furthermore, a
verse
of a, such that a
◦
◦
◦
b
=
b
◦
a for all a
,
b
∈
G.
Roughly speaking, a group is set with one operation and the corresponding in-
verse operation. If the operation is called addition, the inverse operation is subtrac-
tion; if the operation is multiplication, the inverse operation is division (or multipli-
cation with the inverse element).
Z
{
0
,
1
,...,
m
−
}
Example 4.1.
The set of integers
and the operation addition
modulo
m
form a group with the neutral element 0. Every element
a
has an inverse
−
m
=
1
a
)=0mod
m
. Note that this set does not form a group with the
operation multiplication because most elements
a
do not have an inverse such that
aa
−
1
= 1mod
m
.
a
such that
a
+(
−
In order to have all four basic arithmetic operations (i.e., addition, subtraction,
multiplication, division) in one structure, we need a set which contains an additive
and a multiplicative group. This is what we call a field.
Definition 4.3.2
Field
A
field
F is a set of elements with the following properties:
All elements of F form an additive group with the group opera-
tion “+” and the neutral element 0.
All elements of F except 0 form a multiplicative group with the
group operation “
×
” and the neutral element 1.
When the two group operations are mixed, the distributivity law
holds, i.e., for all a
,
b
,
c
∈
F: a
(
b
+
c
)=(
ab
)+(
ac
)
.
Example 4.2.
The set
of real numbers is a field with the neutral element 0 for the
additive group and the neutral element 1 for the multiplicative group. Every real
number
a
has an additive inverse, namely
R
−
a
, and every nonzero element
a
has a
multiplicative inverse 1
/
a
.
