## CIS 628 Introduction to Cryptography## Barbara Nostrand, Ph.D.## Electrical Engineering and Computer Science |

In mathematics, the **characteristic** char(*R*) of a **ring**
*R*, is defined to be the smallest number of times one must add the ring's
*multiplicative identity element* (1) to itself to get the *additive identity*
element (0); the ring is said to have characteristic *zero* if this
repeated sum never reaches the additive identity. That is, char(*R*) is the
smallest positive number *n* such that

if such a number *n* exists, and 0 otherwise. The characteristic may also be taken to be the exponent of the ring's additive group, that is, the smallest positive *n* such that

for every element *a* of the ring (again, if *n* exists; otherwise zero). Some authors do not include the multiplicative identity element in their requirements for a ring (*see rng*), and this definition is suitable for that convention; otherwise the two definitions are easily seen to be equivalent due to the distributive law in rings.

For any **field** *F*, the **ring** of **polynomials** with coefficients in
*F* is denoted by *F*[*x*]. A polynomial
*p*(*x*) in *F*[*x*]
is called **irreducible over F** if it is non-constant and
cannot be represented as the product of two or more non-constant polynomials from

**Galois theory** studies the relationship between a field, its
**Galois group**, and its irreducible polynomials in depth. Interesting and
non-trivial applications can be found in the study of **finite fields**.

Irreducible polynomials are like *prime numbers*: prime numbers are the irreducible
*integers*. They exhibit many of the general properties of the concept *irreducibility*
that also apply to irreducible polynomials, such as the essentially **unique factorization** into
prime or irreducible factors:

Every polynomialp(x) inF[x] can be factorized into polynomials that are irreducible overF. This factorization is uniquepermutationof the factors and multiplication of the factors by constants fromF.

Factorization over a finite field can behave very differently from factorization over the
rational or complex fields. For instance, over the finite field of two elements,
*GF*(2), we have that the polynomial

is not irreducible as it was over or
. This behavior occurs because finite
fields have non-zero <**characteristic**.

Generally, if a polynomial factors over
then the corresponding polynomial with coefficients considered in the finite field
*GF*(*p*) is also reducible, where *p* is a prime (the factors are the factors
over reduced modulo *p*). The converse
of this statement is not true: there are polynomials that factor modulo *p* for all
positive primes *p* but that are not reducible when considered as a polynomial with integer
coefficients. l An example is

*x*^{4}+ 1,

which is irreducible over and
but factors into 4 linear factors or 2
quadratic factors mod any prime *p*.

A **primitive polynomial** is the **minimal polynomial** of a **primitive element** of
the **extension field** GF(*p*^{m}). In other words, a polynomial
*F*(*X*) with coefficients in
GF(*p*) = **Z**/*p***Z** is a **primitive polynomial** if it has a root
α in GF(*p*^{m}) such that
is the entire field GF(*p*^{m}), and moreover,
*F*(*X*) is the smallest degree polynomial having
α as root.

In ring theory, the term
**primitive polynomial** is used for a different purpose, to mean a polynomial over a
**unique factorization domain** (such as the **integers**) whose **greatest common divisor**
of its **coefficients** is a unit. We will use the fact that every **primitive pollynomial**
is **irreducible**. This means that we can use
Peterson's Table of
Irreducible Polynomials over GF(2)
to find our **primitive polynomials**.

Because all minimal polynomials are **irreducible**, all primitive polynomials are also
irreducible.

A primitive polynomial must have a **non-zero constant term**, for otherwise it will be
divisible by *x*. Over the field of two elements, all primitive polynomials have an
odd number of terms, otherwise they are divisible by *x*+*1*.

An irreducible polynomial of degree *m*, *F*(*x*) over GF(*p*) for
prime *p*, is a primitive polynomial if the smallest positive integer *n* such
that *F*(*x*) divides
*x*^{n} - 1 is *n* = *p*^{m} − 1.

Over GF(p^{m}) there are exactly φ(p^{m} − 1)/*m*
**primitive polynomials of degree** *m*, where φ is **Euler's totient function**.

The roots of a primitive polynomial all have order *p*^{m} − 1.

Primitive polynomials define a recurrence relation that can be used to generate **pseudorandom** bits.
In fact every **linear feedback shift register** with maximum cycle (that is 2^{lfsr length}) is related
to a primitive polynomial.

For example, given the primitive polynomial
*x*^{10} + *x*^{3} + 1, we start with a user-specified non-zero bit seed.
We then take the 10th, 3rd, and 0th bits of it, starting from the least significant bit, and
add them together *(mod 2)*, obtaining a new bit. The seed is then shifted left
and the new bit is made the least significant bit of the seed. This process can be repeated to
generate 2^{10}−1 = 1023 random bits.

In general, for a primitive polynomial of degree *m*, this process will generate
2^{m}−1 random bits before repeating the same sequence.

Last modified: 2008 FEB 14 bnostran@syr.edu