Cryptography and Network Security (4th Edition)

2017-07-07 02:10:07

[Page 113]

4.5. Polynomial Arithmetic

Before pursuing our discussion of finite fields, we need to introduce the interesting 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 A zeroth-degree polynomial is called a constant polynomial and is simply an element of the set of coefficients. An nth-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

then addition is defined as

[Page 114]

and multiplication is defined as

where

c_k = a₀b_k1 + a₁b_k1 + ... + a_k1b₁ + a_kb₀

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³ + x² + 2 and g(x) = x² x + 1, where S is the set of integers. Then

f(x) + g(x) = x³ + 2x² x + 3

f(x) g(x) = x³ + x + 1

f(x) x g(x) = x⁵ + 3x² 2x + 2

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

Figure 4.3. Examples of Polynomial Arithmetic

Polynomial Arithmetic with Coefficients in Zp

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.^[5]

^[5] In fact, the set of polynomials whose coefficients are elements of a commutative ring forms a polynomial ring, but that is of no interest in the present context.

[Page 115]

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 Z₇. In this case, we calculate (using Table 4.3c):

5/3 = (5 x 3¹) mod 7 = (5 x 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 x 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 (5x²)/(3x) does not have a solution, because it would require a coefficient with a value of 5/3, which is not in the coefficient set. Suppose that we perform the same polynomial division over Z₇. Then we have (5x²)/(3x) = 4x which is a valid polynomial over Z₇.

However, as we demonstrate presently, even if the coefficient set is a field, polynomial division is not necessarily exact. In general, division will produce a quotient and a remainder:

Equation 4-6

If the degree of f(x) is n and the degree of g(x) is m, (m q(x) m n is and the degree of the remainder is at most m - 1. 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 remainder r(x) in Equation (4.6). 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).

[Page 116]

For the preceding example and [f(x) = x³ + x² + 2 and g(x) = x² 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² x + 1) + x = (x³ + x² x + 2) + x

= x³ + x² + 2 = f(x)

For our purposes, polynomials over GF(2) are of most interest. Recall from Section 4.4 that in GF(2), addition is equivalent to the XOR operation, and multiplication 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⁷ + x⁵ + x⁴ + x³ +x + 1) and g(x) = (x³ + x + 1), the figure shows f(x) + g(x); f(x) g(x); f(x) x g(x); and f(x)/g(x). Note that g(x)|f(x)

Figure 4.4. Examples of Polynomial Arithmetic over GF(2)

[Page 117]

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 polynomial^[6] f(x) = x⁴ + 1 over GF(2) is reducible, because x⁴ + 1 = (x + 1)(x³ + x² + x + 1)

^[6] In the remainder of this chapter, unless otherwise noted, all examples are of polynomials over GF(2).

Consider the polynomial f(x) = x³ + 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

c(x) divides both a(x) and b(x);

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 divisor of two polynomials. The equality in Equation (4.4) can be rewritten as the following theorem:

Equation 4-7

[Page 118]

The Euclidean algorithm for polynomials can be stated as follows. The algorithm assumes that the degree of a(x) is greater than the degree of b(x). Then, to find gcd[a(x), b(x)],

EUCLID[a(x), b(x)] 1. A(x) x); B(x) x) 2. if B(x) = 0 return A(x) = gcd[a(x), b(x)] 3. R(x) = A(x) mod B(x) 4. A(x) B(5. B(x) R(6. goto 2

Find gcd[a(x), b(x)] for a(x) = x⁶ + x⁵ +x⁴ + x³ + x² +x + 1 and b(x) = x⁴ + x² + x + 1.

A(x) = a(x); B(x) = b(x)

R(x) = A(x) mod B(x) = x³ + x² + 1

A(x) = x⁴ + x² + x + 1; B(x) = x³ + x² + 1

R(x) = A(x) mod B(x) = 0

gcd[a(x), b(x)] = A(x) = x³ + x² + 1

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 performed 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.

[Page 119]

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ⁿ.