For a given prime, p, we define the finite field of order p, GF(p), as the set Zp of integers {0, 1, ..... , p - 1} together with the arithmetic operations modulo p.

**FINITE FIELDS OF
THE FORM GF(p)**

In
Section 4.4, we defined a field as a set that obeys all of the axioms of Figure
4.2 and gave some examples of infinite fields. Infinite fields are not of
particular interest in the context of cryptography. However, finite fields play
a crucial role in many cryptographic algorithms. It can be shown that the order
of a finite field (number of elements in the field) must be a power of a prime *p ^{n}*,
where

We
discuss prime numbers in detail in Chapter 8. Here, we need only say that a
prime number is an integer whose only positive integer factors are itself and
1. That is, the only positive integers that are divisors of *p* are *p*
and 1.

The
finite field of order *p ^{n}* is generally written GF(

**Finite
Fields of Order p**

For a
given prime, *p*, we define the finite field of order *p*, GF(*p*),
as the set Z* _{p}* of integers {0, 1, ..... ,

Recall
that we showed in Section 4.3 that the set Z* _{n}* of integers {0,
1, ..... ,

Because *w* is
relatively prime to *p*, if we multiply all the elements of Z* _{p}*
by

Table 4.5
shows arithmetic operations in GF(7). This is
a field of order 7 using modular arithmetic modulo 7. As can be seen, it
satisfies all of the properties required of a field (Figure 4.2). Compare this
table with Table 4.2. In the latter case, we see that the set Z8,
using modular arithmetic modulo 8, is not a field. Later in this chapter,
we show how to define addition and multiplication operations on Z8 in such
a way as to form
a finite field.

Finding the
Multiplicative Inverse in GF(*p*)

It is easy to find the multiplicative inverse of an element in GF(*p*) for small
values of

*p.
*You simply construct a multiplication table,
such as shown
in Table 4.5b, and the
desired result can be read directly.
However, for large values of *p*, this approach is not practical.

**Table 4.5
**Arithmetic in
GF(7)

If *a *and *b *are relatively prime, then
*b *has a multiplicative inverse modulo *a*. That
is, if gcd(*a*, *b*)
= 1, then *b *has a multiplicative inverse
modulo *a*. That is,
for positive integer *b *6 *a*,
there exists a *b *- 1 6 *a *such
that *bb *- 1 = 1
mod *a*. If *a *is a prime number and *b *6 *a*,
then clearly *a *and *b *are relatively prime and have a
greatest common divisor of 1. We now
show that we can easily compute *b *- 1 using
the extended Euclidean algorithm.

We repeat here Equation (4.7), which we showed can be solved with the
extended Euclidean algorithm:

*ax *+ *by *=
*d *=
gcd(*a*, *b*)

Now, if gcd(*a*, *b*) = 1, then
we have *ax *+ *by *= 1. Using the basic equalities of mod- ular arithmetic, defined in Section
4.3, we can say

[(*ax *mod *a*)
+ (*by *mod *a*)] mod *a *=
1 mod *a*

0 + (*by *mod *a*) = 1

But if *by *mod *a *= 1, then *y *= *b *- 1. Thus, applying the extended Euclidean
algorithm to Equation (4.7) yields the value of the multiplicative inverse of *b *if
gcd(*a*, *b*) = 1. Consider the example that was shown in Table 4.4.
Here we have *a *= 1759, which is a prime number,
and *b *= 550. The solution of the equation 1759*x *+ 550*y *= *d *yields a value of *y *= 355. Thus, *b *- 1 = 355. To
verify, we calculate 550 355 mod 1759 = 195250 mod 1759 = 1.

More generally, the extended Euclidean algorithm can be used to find a
multi- plicative inverse in Z*n *for any *n*. If we apply the extended Euclidean algorithm to the equation *nx *+ *by *= *d*, and the algorithm yields *d *= 1, then *y *= *b *- 1 in Z*n*.

Summary

In this section, we have shown how to construct a finite field of order *p*, where *p *is prime. Specifically, we defined GF(*p*) with the following properties.

**1.
**GF(*p*)
consists of *p *elements.

**2.
**The binary operations + and x are defined
over the set. The operations of addi-
tion, subtraction, multiplication, and division can be performed without leav- ing
the set. Each element of the set other than 0 has a multiplicative inverse.

We have shown that the elements of GF(*p*) are the integers {0, 1, ..... , *p *- 1} and
that the arithmetic operations are addition and multiplication mod *p*.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

: Finite Fields Of The Form GF(p) |

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.