Cryptography: Polynomial Arithmetic

•Why study polynomial arithmetic?

•Defining finite fields over sets of polynomials will allow us to create a finite set of numbers that are particularly appropriate for digital computation. Since these numbers will constitute a finite field, we will be able to carry out all arithmetic operations on them — in particular the operation of division — without error.

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.

Polynomial Arithmetic with Coefficients in Zp  

•Let us now consider polynomials in which the coefficients are elements of some field F;

–Referred 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, then

  5/3 = (5 * 3-1)mod7 = (5 * 5)mod7 = 4

•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 (5x2)/(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 Z7. Then we have (5x2)/(3x) = 4x, which is a valid polynomial over Z7.

•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

  f(x) = q(x)g(x) + r(x)

with polynomial degrees:

–Degree f(x) = n
Degree g(x) = m
Degree q(x) = n - m
Degree r(x) <= 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). 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).

•Example [f(x) = x3 + x2 + 2 and g(x) = x2 - x + 1], f(x)/g(x) produces a quotient of q(x) = x + 2 and a remainder r(x) = x.

•This is easily verified by noting that

q(x)g(x) + r(x)

= (x+2) (x2 -x+1) + x

= (x3 +x2 -x+2) + x

= x3 +x2 +2

= f(x)

•For our purposes, polynomials over GF(2) are of most interest.

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

•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 f(x) = x4 + 1 over GF(2) is reducible, because x4 + 1 = (x + 1)(x3 + x2 + x + 1).