Cryptography Reference
In-Depth Information
"Î
there exists an element
aG
¢
Î
such that
(iv) Inverse element:
aG
,
¢ ¢
*=*=
(3.4)
aa
a a e
(v) In addition, a group
G
is
abelian
if it satisfies the following property:
"Î
Commutative:
,
ab
G
,
*=*
(3.5)
ab ba
If the identity element in the group is 0 and the inverse of
a
is -
a
, then the group
is denoted as an additive group. Similarly, if the identity element in the group is 1 and
the inverse of
a
is
a
-1
, the group is denoted as a multiplicative group.
If |
G
| is finite, then the group
(,)
G
*
is finite. Furthermore, the
order
of a group is
defined as the number of elements in the finite group.
If
a
Î
then let
k
be the least positive integer such that
a
k
= 1, provided
k
exists.
Then the
order
of
a
[ord(
a
)] is defined to be
k
. If
k
does not exist, the
order
of
a
is
defined to be infinity,
¥
.
An example of a group is a set of integers (
Z
) with an additive operation. Let
Z
n
denote
Z
/
nZ
(integer modulo
n
). Meanwhile, not all elements of the set
Z
n
under multiplication modulo
n
have multiplicative inverses. Hence, set
Z
n
under
multiplication modulo
n
is not a group. However,
,
*
n
Z
(multiplicative group of
Z
n
)
=Î
=
In particular, if
n
is a prime, then the set of elements in
{
aZ dan
|
( ,
)
1}.
n
*
n
££-
.
Z
includes the range
1
an
1
Cyclic group:
A group
G
is
cyclic
if every element in it can be expressed as a power of a fixed element.
For example, if
a
Î
is a fixed element, then every element in
G
can be expressed in
the form
a
k
, where
k
∈
Z
(integers). Hence,
a
is the generator of the group
G
. Note that
every subgroup in a cyclic group is cyclic.
Lagrange's theorem:
If
H
is a subgroup of
G
, then the order of
H
(|
H
|) divides the order of
G
(|
G
|).
Consequently, if
a
Î
then ord(
a
)
divides |
G
|, provided ord(
a
)
exists.
,
3.2.2 Rings
R
+´
is a set
R
with binary operations, namely, addition (
+
) and multipli-
cation (
´
), on
R
and satisfying the following properties:
A ring
(, ,)
(i) Closure under multiplication
"Î
,
ab
R
´Î
ab R
(3.6)
Search WWH ::
Custom Search