Cryptography Reference
In-Depth Information
According to the first requirement, the operation
∗
1
must be commutative (this
is not required for the operation
∗
2
). The ring is called
commutative
(
noncommuta-
tive
) if the operation
∗
2
is (not) commutative.
are commutative rings that are further
addressed in Sections 3.2 (entitled “Integer Arithmetic”) and 3.3 (entitled “Modular
Arithmetic”).
9
Similarly,
For example,
Z
,
+
,
·
and
Z
n
,
+
,
·
Q
,
+
,
·
and
R
,
+
,
·
are commutative rings. Also, the set
of real-valued
n
n
matrices form a ring with the zero matrix as the identity element
of addition and the identity matrix as the identity element of multiplication. Contrary
to the previous examples, this ring is noncommutative.
×
3.1.2.5
Fields
If we have a ring
is a group (instead of a
monoid), then we have a
field
. This is formally expressed in Definition 3.17.
S,
∗
1
,
∗
2
and require that
S
\{
e
1
}
,
∗
2
Definition 3.17 (Field)
Aring
S,
∗
1
,
∗
2
in which
S
\{
e
1
}
,
∗
2
is a group is a
field
.
Another way of saying that
S
\{
e
1
}
,
∗
2
is a group is that every nonidentity
element (with respect to
∗
1
) must have an inverse element (with respect to
∗
2
).
Afield
S,
∗
1
,
∗
2
is
finite
if it contains only finitely many elements (i.e.,
|
). Finite fields have many applications in cryptography. For example, they
are frequently used in public key cryptography. More surprisingly, they are also used
in new symmetric encryption systems, such as the AES addressed in Section 10.2.2.
All finite fields with
n
elements can be shown to be structurally equivalent
or isomorphic (see Section 3.1.3 for the notion of isomorphic algebraic structures).
Consequently, it is sufficient to consider and thoroughly examine only one finite field
with
n
elements. This field is called
Galois field
,
10
S
|
<
∞
F
n
or
GF
(
n
).For
every prime number
p
, there is a finite field with
p
elements (i.e.,
denoted by
F
p
)andaseries
of finite fields with
p
n
elements for every positive integer
n
(see Section 3.3.6). In
the simplest case,
p
=2and
F
2
consists of only two elements, namely the identity
elements of the two binary operations (i.e., the zero element and the unity element).
Similar to Definition 3.12, we can introduce the notion of a subfield as
suggested in Definition 3.18.
Definition 3.18 (Subfield)
A subset
H
of a field
F
is a
subfield
of
F
if it closed
under the operations of
F
and also forms a field.
9If
n
is prime, then
Z
n
,
+
, ·
is a field.
10
The term was chosen in honor of Evariste Galois, who lived from 1811 to 1832. Galois is said to
have found all finite fields.
