Cryptography Reference
In-Depth Information
(
,
)
=
gcd
f
g
1 and the extended Euclidean algorithm allows us to compute polyno-
,
∈ Z
p
[
]
=
+
≡
(
)
mials
s
t
x
such that 1
sf
tg
. Then 1
tg
mod
f
and hence
t
mod
f
is the inverse of
g
in
Z
p
[
x
]
f
.
The following table summarizes the parallelism between the constructions of
Z
q
and
Z
2
[
x
]
f
:
Ring
Z
Z
p
[
x
]
Element
q
∈ Z
,
q
≥
2
f
∈ Z
p
[
x
]
,
deg
(
f
)
=
n
>
0
Quotient ring
Z
q
={
0
,
1
,...,
q
−
1
}
Z
p
[
x
]
={
g
∈
Z
p
[
x
]|
deg
(
g
)<
n
}
f
Field
Z
q
field iff
q
prime
[
x
]
f
field iff
f
irreducible
Z
p
Remarks 2.5
Theorem 2.22 shows that for each prime
p
and each irreducible poly-
nomial of degree
n
in
there exists a field of order
p
n
. It can be shown that, for
each prime
p
and each positive integer
n
, there is always an irreducible polynomial
of degree
n
in
Z
p
[
x
]
, so that there is always a field of order
p
n
. Moreover, every
finite field has order
p
n
Z
p
[
x
]
0 as a consequence
of Exercise 2.29. Note that there may be several distinct irreducible polynomials of
degree
n
in
for some prime
p
and some integer
n
>
]
f
. However,
all these fields are isomorphic and this allows us to speak of
the
finite field of order
p
n
which is denoted by
Z
p
[
x
]
, and each of them gives rise to a different field
Z
p
[
x
p
n
(where the initials
GF
stand for “Galois
Field”). We emphasize, however, that in cryptographic applications, the irreducible
polynomial used to construct the field is explicitly defined in order to obtain exactly
the same multiplication.
F
p
n
or by
GF
(
)
Examples 2.5
1. Let
f
=
x
∈ Z
p
[
x
]
. Then
f
is irreducible and
Z
p
[
x
]
f
is a field of order
p
.In
this case
1, i.e., the constant
polynomials. The polynomial operations on these constant polynomials are the
same as the operations of these elements when regarded as elements of
Z
p
[
x
]
f
consists of the polynomials of degree
<
Z
p
. Thus
we see that, in this case,
Z
p
[
x
]
f
= Z
p
. As mentioned above, often the notation
F
p
is used (instead of
Z
p
) to denote this field.
x
2
2. Let
f
]
f
is simply the field of
4 elements constructed at the beginning of this section and the multiplication is
given by the previously defined Maple function
mult4
.
3. Let us use Maple to build the multiplication table of the finite field of 9 elements.
We first find an irreducible polynomial of degree 2 in
=
+
x
+
1
∈ Z
2
[
x
]
. Then the field
F
4
= Z
2
[
x
Z
3
[
x
]
:
> IrreduciblePolynomial(3, 2);
xˆ2 + 1
x
2
The multiplication in
Z
3
[
x
]
f
, where
f
=
+
1, will be given by the following
function:
> mult9 := (f, g) -> Rem(f*g, xˆ2+1, x) mod 3:
