Cryptography Reference
In-Depth Information
finite field is also called the
order
of the field). This result, however, leaves open
the question whether there are other finite fields. Although
Z
4
is not a field, one can
easily check that if we consider the set
{
0
,
1
,
2
,
3
}
with addition and multiplication
defined by the following tables:
⊕
0123
0 0123
1 1032
2 2301
3 3210
0123
0 0000
1 0123
2 0231
3 0312
·
then we have a field of order 4 (note that we have not used the notation
Z
4
because
we reserve it for the ring of residue classes modulo 4, which, as mentioned, is not a
field). Thus we see that, in addition to the fields
Z
p
with
p
prime (the finite
prime
fields
) there are other fields. But if we attempt in a similar way to find a field on
the set
we fail: this set cannot be given a field structure, or, in other
words, there are no fields with exactly 6 elements. With a little patience one might
carry out this experiment but it is really not necessary because, as the next exercise
shows, there are no fields of order 6 (for more details one may consult an introductory
algebra text such as [45], [48] or, more specifically, a textbook on finite fields such
as [131]).
{
0
,
1
,
2
,
3
,
4
,
5
}
Exercise 2.29
(i) Show that if
F
is a finite field, then the least positive integer
m
such that
1
+
1
+···+
1
=
0 is a prime number
p
(called the
characteristic
of
F
).
m
times
F
(ii) Show that the set of the elements of a finite field
that can be obtained by
adding 1 a finite number of times is a field with the operations induced by
those of
F
(i.e., a subfield). Show that this subfield is isomorphic to
Z
p
, where
p
is the characteristic of
F
, so that it is a prime field called the prime subfield
.
(iii) Show that
of
F
has a natural structure of a vector space over its prime subfield so
that if the dimension of this vector space is
n
, then
F
p
as
vector spaces (similarly to the way each finite-dimensional real vector space is
isomorphic to some
F
is isomorphic to
Z
n
). Deduce that
p
n
, where
p
is the characteristic
R
|F|=
of
F
, and hence that the order of a finite field is always a prime power.
2.8.1.1. The
BitXor
Operation
The field of order 4 we have just constructed has characteristic 2 and, as we shall
soon see, addition in these fields is given by the bitwise Xor operation, which we
are going to implement in a Maple function called
BitXor
and plays an important
