Polynomial arithmetic in which the coefficients are in GF(p), and the polynomials are defined modulo a polynomial m(x) whose highest power is some integer n.

**POLYNOMIAL
ARITHMETIC**

Before continuing our discussion of finite fields,
we need to introduce the interest-
ing subject of polynomial arithmetic. We are concerned with polynomials in a single variable *x*, and we can distinguish three
classes of polynomial arithmetic.

•
Ordinary polynomial arithmetic, using the basic rules
of algebra.

•
Polynomial
arithmetic in which the arithmetic on the coefficients is performed modulo *p *; that is, the coefficients are in GF(*p*).

•
Polynomial arithmetic
in which
the coefficients are in
GF(*p*), and the polynomials are defined
modulo a polynomial *m*(*x*)
whose highest power is some integer
*n*.

This section examines the first two classes,
and the next section covers the last
class.

Ordinary Polynomial Arithmetic

A **polynomial **of
degree *n *(integer *n *>= 0) is an expression of the form

where the *a**i *are elements of some
designated set of numbers *S*, called
the **coefficient set**, and *a**n *!= 0. We say that such polynomials are defined over the coefficient set *S*.

A zero-degree
polynomial is called a **constant
polynomial **and is simply an element of the set of coefficients. An *n*th-degree polynomial is said to be a **monic polynomial **if *a**n *= 1.

In the context
of abstract algebra,
we are usually not interested in evaluating a

polynomial
for a particular value of *x *[e.g.,
*f*(7)]. To emphasize this point, the variable

*x *is sometimes referred to as the **indeterminate**.

Polynomial arithmetic includes the
operations of addition, subtraction, and multiplication. These operations are defined in a natural
way as though the variable
*x** *was
an element of *S*. Division is
similarly defined, but requires that *S *be a field. Examples of fields include
the real numbers,
rational numbers, and Z*p *for *p *prime. Note that the set of all integers
is not a field and does not support polynomial division.

Addition and subtraction are performed
by adding or subtracting corresponding
coefficients. Thus, if

In the last formula, we treat *a**i *as zero for *i *> *n *and *b**i *as zero for *i *> *m*. Note that the degree of the product
is equal to the sum of the degrees of the two polynomials.

**As an example, let ***f***(***x***) ****= ***x*3 **+ ***x*2 **+ ****2 and ***g***(***x***) ****= ***x*2 **- ***x ***+ ****1, where S is the
set of integers. Then**

*f***(***x***) ****+ ***g***(***x***) ****= ***x***3 ****+ ****2***x***2 ****- ***x ***+ ****3**

*f***(***x***) ****- ***g***(***x***) ****= ***x***3 ****+ ***x ***+ ****1**

*f***(***x***) ***** ***g***(***x***) ****= ***x***5 ****+ ****3***x***2 ****- ****2***x ***+ ****2**

**Figures 4.3a through 4.3c show the manual calculations. We comment
on division subsequently.**

Polynomial Arithmetic with Coefficients in Z*p*

Let us now consider polynomials in which the
coefficients are elements of some field
F; we refer to this as a polynomial over the field F. In that case, it is easy to show that the set of such
polynomials is a ring, referred to as a **polynomial
ring**. That is, if we consider each distinct polynomial to be an element of
the set, then that set is a ring.

When polynomial arithmetic is performed on
polynomials over a field, then division is possible. Note that this does not
mean that *exact division *is possible.
Let us
clarify this distinction. Within a field, given two elements *a *and *b*, the quotient *a*/*b*is also an element
of the field. However, given a ring *R *that is not a field, in

general, division will result in both a quotient and a remainder;
this is not exact division.

**Consider
the division 5/3 within a set ***S***. If ***S ***is the set of rational numbers, which is a field, then the
result is simply expressed as 5/3 and is an element of S. Now suppose that S is
the field Z7**

**5/3
= (5 ***** ****3 - 1****) mod 7 = (5 ***** ****5) mod 7 = 4**

**which ****is an exact solution. Finally,
suppose that S is the set of integers, which is a ring but not a field. Then
5/3 produces a quotient of 1 and a remainder of
2:**

**5/3 =
1 + 2/3**

**5 = 1 ***** ****3 + 2**

**Thus, division is
not exact over the set of integers**

Now, if we attempt to perform polynomial division over a
coefficient set that is not a field, we find that division is not always defined.

**If the coefficient
set is the integers, then (5 x**

However, as we demonstrate presently, even if
the coefficient set is a field, poly- nomial division is not necessarily exact. In general, division will produce a quotient and a remainder. We can restate the division algorithm of Equation
(4.1) for polynomials over a
field as follows. Given polynomials *f*(*x*)
of degree *n *and *g*(*x*) of degree (*m*),
(*n *Ú *m*), if we divide *f*(*x*)
by *g*(*x*), we get a quotient *q*(*x*)
and a remainder *r*(*x*) that obey the relationship

With the understanding that remainders are allowed,
we can say that polynomial division is possible
if the coefficient set is a field.

In an analogy
to integer arithmetic, we can write
*f*(*x*) mod *g*(*x*) for the remain-
der *r*(*x*) in Equation (4.10). That is, *r*(*x*)
= *f*(*x*) mod *g*(*x*). If there is no remainder [i.e., *r*(*x*) = 0], then we can say *g*(*x*) **divides ***f*(*x*), written as *g*(*x*) ƒ *f*(*x*). Equivalently, we can say that
*g*(*x*) is a **factor **of *f*(*x*) or *g*(*x*) is a **divisor
**of *f*(*x*).

For the preceding
example [*f*(*x*) = *x*3 + *x*2 + 2 and *g*(*x*) = *x*2 - *x *+ 1], *f*(*x*)/*g*(*x*) produces a quotient of *q*(*x*)
= *x *+ 2 and a remainder *r*(*x*)
= *x*, as shown in Figure 4.3d. This is
easily verified by noting that

*q*(*x*)*g*(*x*)
+ *r*(*x*) = (*x *+ 2)(*x*2 - *x *+ 1) + *x *= (*x*3 + *x*2 - *x *+ 2) + *x*

= *x*3 + *x*2 + 2 =
*f*(*x*)

For our purposes,
polynomials over GF(2) are
of most interest.
Recall from Section 4.5 that in GF(2), addition is equivalent to the XOR
operation, and multi- plication is equivalent to the logical AND operation.
Further, addition and subtraction are equivalent mod 2: 1 + 1 = 1 - 1 = 0; 1 +
0 = 1 - 0 = 1; 0 + 1 = 0 - 1 = 1.

**Figure 4.4 shows
an example of polynomial
arithmetic over GF(2). For f(x)
= (x**

A polynomial *f*(*x*)
over a field *F *is
called **irreducible **if and only if *f*(*x*)
cannot be expressed as a product of two polynomials, both over *F*, and both of degree lower than that of *f*(*x*).
By analogy to integers, an irreducible polynomial is also called a **prime polynomial**.

The polynomial9
*f*(*x*) = *x*4 + 1
over GF(2) is reducible, because

*x*4 + 1 = (*x *+ 1)(*x*3 + *x*2 + *x *+ 1).

Consider the polynomial *f*(*x*) = *x*3 + *x *+ 1.
It is clear by inspection that *x *is
not a factor of *f*(*x*).
We easily show that *x *+ 1 is not a factor of *f*(*x*):

Thus, *f*(*x*)
has no factors of degree 1. But it is clear by inspection that if *f*(*x*)
is reducible, it must have one factor of degree 2 and one factor of degree 1.
Therefore, *f*(*x*) is irreducible.

Finding the Greatest Common Divisor

We can extend the analogy
between polynomial arithmetic over a field and integer arithmetic by defining the greatest common
divisor as follows.
The polynomial *c*(*x*)
is said to be the greatest common
divisor of *a*(*x*) and *b*(*x*) if the following are true.

**1.
***c*(*x*) divides both *a*(*x*) and *b*(*x*).

**2.
**Any divisor of *a*(*x*)
and *b*(*x*) is a divisor of *c*(*x*).

An equivalent definition is the following: gcd[*a*(*x*), *b*(*x*)] is the polynomial of maximum degree that divides both *a*(*x*) and *b*(*x*).

We can adapt the Euclidean algorithm to compute
the greatest common divi- sor of two
polynomials. The equality in
Equation (4.6) can be rewritten as the fol- lowing theorem.

gcd[*a*(*x*), *b*(*x*)]
= gcd[*b*(*x*), *a*(*x*) mod
*b*(*x*)] **(4.11)**

Equation (4.11) can be used repetitively to determine the
greatest common divisor. Compare the following scheme
to the definition of the Euclidean algorithm for integers.

At each iteration, we
have *d*(*x*) = gcd(*r**i *+ 1(*x*), *r**i*(*x*)) until
finally *d*(*x*) = gcd(*r**n*(*x*), 0) = *r**n*(*x*).
Thus, we can find the greatest common
divisor of two integers by repetitive application of the division algorithm.
This is the Euclidean algorithm for
polynomials. The algorithm assumes
that the degree of *a*(*x*) is greater than the degree of *b*(*x*).

Summary

We began this section with a discussion of arithmetic with ordinary polynomials. In ordinary polynomial arithmetic, the variable is not evaluated; that is, we do not plug a
value in for the variable
of the polynomials. Instead, arithmetic operations are per- formed on polynomials (addition,
subtraction, multiplication, division) using the
ordinary rules of algebra. Polynomial division is not allowed unless the coefficients are elements of a field.

Next, we discussed polynomial arithmetic in which the coefficients are elements
of GF(*p*). In this case,
polynomial addition, subtraction, multiplication, and division are allowed. However, division is
not exact; that is, in general
division results in a quotient and a remainder.

Finally, we showed that the Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements
of a field. All of the material in this section
provides a foundation for the following section,
in which polynomials are
used to define finite fields of order *p**n*.

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

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Basic Concepts in Number Theory and Finite Fields : Polynomial Arithmetic |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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