Cryptography Reference
In-Depth Information
In cryptography, we are almost always interested in fields with a finite number of
elements, which we call finite fields or Galois fields. The number of elements in the
field is called the
order
or
cardinality
of the field. Of fundamental importance is the
following theorem:
Theorem 4.3.1
A field with order m only exists if m is a prime
power, i.e., m
=
p
n
, for some positive integer n and prime integer
p. p is called the
characteristic
of the finite field.
This theorem implies that there are, for instance, finite fields with 11 elements,
or with 81 elements (since 81 = 3
4
) or with 256 elements (since 256 = 2
8
,and2is
a prime). However, there is no finite field with 12 elements since 12 = 2
2
3, and
12 is thus not a prime power. In the remainder of this section we look at how finite
fields can be built, and more importantly for our purpose, how we can do arithmetic
in them.
·
4.3.2 Prime Fields
The most intuitive examples of finite fields are fields of prime order, i.e., fields with
n
= 1. Elements of the field
GF
(
p
) can be represented by integers 0
,
1
,...,
p
1. The
two operations of the field are modular integer addition and integer multiplication
modulo p
.
−
Theorem 4.3.2
Let p be a prime. The integer ring
Z
p
is denoted
as GF
(
p
)
and is referred to as a
prime field
,orasa
Galois field
with a prime number of elements. All nonzero elements of GF
(
p
)
have an inverse. Arithmetic in GF
(
p
)
is done modulo p.
Z
m
which was introduced in
Sect. 1.4.2, i.e., integers with modular addition and multiplication, and
m
happens
to be a prime,
This means that if we consider the integer ring
Z
m
is not only a ring but also a finite field.
In order to do arithmetic in a prime field, we have to follow the rules for integer
rings: Addition and multiplication are done modulo
p
, the additive inverse of any
element
a
is given by
a
+(
a
)=0mod
p
, and the multiplicative inverse of any
nonzero element
a
is defined as
a
−
a
−
1
= 1. Let's have a look at an example of a
·
prime field.
Example 4.3.
We consider the finite field
GF
(5)=
. The tables below
describe how to add and multiply any two elements, as well as the additive and
{
0
,
1
,
2
,
3
,
4
}
