Cryptography Reference
In-Depth Information
A
. In this case we formally call this partition the
quotient
of
A
by
R
and denote it by
A
/
R
.
6.1.2 Groups
Formally, a
group
is any set
G
associated to a group law which is a mapping from
G
G
to
G
. It thus maps two operands from
G
onto an element of
G
. This law can be denoted
either additively (with the
×
, the dot symbol, or
even nothing). Using multiplicative notation, this law must fulfill the following group
properties.
+
symbol) or multiplicatively (with
×
1.
Closure
: For any
a
,
b
∈
G
,
ab
is an element of
G
.
2.
Associativity
: For any
a
(
ab
)
c
.
3.
Neutral element
: There exists a distinguished element
e
in
G
such that for any
a
,
b
,
c
∈
G
,wehave
a
(
bc
)
=
∈
=
=
G
,wehave
ae
ea
a
.
4.
Invertibility
: For any
a
∈
G
, there exists an element
b
∈
G
such that
ab
and
ba
are neutral elements.
It is further easy to see that the neutral element
e
is necessarily unique: if
e
and
e
are
neutral, we must have
e
e
ee
=
e
because
e
is neutral, and
ee
=
e
e
=
=
e
because
e
is neutral, therefore
e
e
. We usually denote this neutral element by 1 (or 0 if
the group law is additively denoted). This implies that if
b
is an inverse of
a
, then
ab
=
1. It is not more difficult to see that the inverse of an element is unique: if
b
and
b
are both inverse of
a
, we must have
ab
=
ba
=
1 and
ab
=
b
a
=
ba
=
=
1. We can
then multiply the latter equality by
b
to the right and obtain (
b
a
)
b
=
1
.
b
=
b
which
implies
b
(
ab
)
b
by associativity, and then
b
=
a
−
1
=
b
. We usually denote by
b
=
the
inverse
of
a
(or
a
if the group law is additively denoted, in which case the term
opposite
is more appropriate).
−
ba
. Usually, additively
denoted groups are commutative. When a group is commutative, we say it is an
Abelian
group
.
Commutativity
means that for any
a
,
b
∈
G
,wehave
ab
=
We notice that all products made of a single element
a
are uniquely defined by
their number of terms: for instance (
a
(
a
(
aa
)))
a
=
a
(((
aa
)
a
)
a
). We can thus uniquely
denote it by
a
5
(or 5
a
with additive notations). We can also define
a
−
n
as the inverse
of
a
n
. (With additive notations, this is denoted
n
.
a
as a multiplication of an integer by
a group element.)
Here are a few fundamental examples.
The
trivial group G
={
0
}
defined by 0
+
0
=
0. There is not much to say about
this group.
The Abelian group
Z
of
relative integers
with the usual addition law. We notice
that this is the
free Abelian group
generated by a single element
g
=
1: all
elements can be uniquely written
ng
.
Search WWH ::
Custom Search