Cryptography Reference
In-Depth Information
The
symmetric group
S
A
over a given set
A
. This is the set of all permutations over
A
with the composition law which is usually denoted
◦
. When
A
={
1
,
2
,...,
n
}
,
we denote it
S
n
. Note that this is not an Abelian group when
n
≥
3.
The
group
Z
n
of residues modulo n
. This is the group
{
0
,
1
,...,
n
−
1
}
with the
additive law
(
a
,
b
)
→
a
+
b
mod
n
.
We do not encourage denoting it as
a
b
in cryptography since this may lead
to confusions with other modular additions, or even the regular one.
+
We recall that
x
mod
n
denotes the
remainder
in the
Euclidean division
of
x
by
n
: computing the division of
x
by
n
, we obtain an integral relation
x
=
qn
+
r
with
0
n
. The
x
mod
n
integer is simply
r
. The quotient
q
is the greatest integer
which is smaller than
≤
r
<
n
. We can denote it
r
. We can thus write
x
x
n
x
mod
n
=
x
−
×
n
.
6.1.3 Generating a Group, Comparing Groups
If we take a subset
A
of a group
G
, we say that
A generates G
, or is a generator set,
if any element of
G
can be written as a finite product (or sum for additive notations)
of elements which are taken only from
A
or the inverse (or opposite) of elements of
A
. For instance,
generates
Z
as a group since all relative integers are finite sums of
terms all equal to 1 or to
{
1
}
−
1, the inverse of 1. It also generates
Z
n
with the modulo
n
addition.
A
group (homo)morphism
is a function
f
from a group
G
(whose neutral element
is 1
G
) to a group
G
(whose neutral element is 1
G
) with the following properties:
1. If 1
G
is the neutral element of
G
, then
f
(1
G
) is neutral in
G
;
2. For all
a
,
b
∈
G
,wehave
f
(
ab
)
=
f
(
a
)
f
(
b
) (here,
ab
is a
G
-product and
f
(
a
)
f
(
b
)isa
G
-product);
3. For all
a
G
,wehave
f
(
a
−
1
)
f
(
a
)
−
1
(here,
a
−
1
is a
G
-inverse and
f
(
a
)
−
1
∈
=
is a
G
-inverse).
We notice that the first and third properties are consequences of the second one.
We can define the kernel
f
−
1
(
{
1
G
}
)of
f
as the reciprocal image of the set
{
1
G
}
by
G
such that
f
(
a
) is neutral in
G
. We can also define the image
f
(
G
)of
f
as the set of all elements reached by
f
. We have the following properties:
∈
f
: it is the set of all
a
f
is injective if and only if
f
−
1
(
{
1
G
}
)
={
1
G
}
;
G
.
f
is surjective if and only if
f
(
G
)
=
When a group morphism is injective and surjective, it is bijective, thus called a
group
isomorphism
. In that case we say the groups are
isomorphic
, and considered as having
the same group structure.
Search WWH ::
Custom Search