Cryptography Reference
In-Depth Information
9.2.1 Preliminaries
A group
⊕
defined on
G
such that it is closed, associative, each element of
G
has an inverse,
and has an identity element. Moreover, the group is called commutative or abelian
if
(
G
,
⊕
)
, written additively, is a set
G
associated with a binary operation
is commutative. For a finite group, the number of elements is referred to as the
group order
or
cardinality
. On the other hand, the order of an element
a
in a finite
group
G
, denoted by ord
G
(
⊕
a
)
, is the smallest integer
c
such that
ca
=
a
⊕
a
⊕···⊕
a
=
0
c
times
where 0 commonly represents the identity element of
⊕
. The order of a group is
divisible by the order of any of its elements.
Aring
(
R
,
⊕
,
⊗
)
is a set
R
associated with two binary operations,
⊕
and
⊗
,
defined on
R
such that
(
R
,
⊕
)
is an commutative group and
⊗
is closed, associative
and distributive over
⊕
. Furthermore, the ring is commutative if
⊗
is commutative.
Inaring
R
, if the operation
⊗
has an identity element the ring is called a ring with
identity. The operation
is usually written multiplicatively and its identity, if one
exists, is denoted by 1. An example of a commutative ring with identity is the set
Z
n
={
⊗
under addition and multiplication modulo
n
.
In a ring with identity
R
, if the nonzero elements form a commutative group
under
0
,
1
,...,
n
−
1
}
, then
R
is a field. In other words, a field can be seen as a commutative group
with respect to two binary operations such that one operation is distributive over the
other. While the set of rational numbers
⊗
is an example of
a ring that is not a field since the only elements that have multiplicative inverses are
1 and
Q
is an example of a field,
Z
1. A field that has a finite number of elements is called a finite field, and can be
either a prime field or an extension field. As the name indicates, a prime field
−
F
p
has
a prime cardinality
p
. An extension field, on the other hand, has a cardinality of
p
d
,
where
p
is prime and
d
>
1 is an integer. Such a field is created by extending
the prime field
F
p
where
d
denotes the extension degree. The characteristic of both
F
p
and
,is
p
. An interesting fact is that all finite fields
of the same cardinality are isomorphic, i.e., have the same structure even if they
are represented differently. In other words, these fields can be made identical by
renaming their elements.
F
p
d
, denoted by char
(
F
p
)
9.2.2 The Elliptic Curve Group
An elliptic curve
E
over a
fie
ld
K
, whose algebraic closure is denoted by
K
,isthe
set of points
(
x
,
y
)
,
x
,
y
∈
K
, that satisfy the Weierstrass equation
y
2
x
3
a
2
x
2
E
:
+
a
1
xy
+
a
3
y
=
+
+
a
4
x
+
a
6
(9.1)
