CIS 628 Introduction to Cryptography

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Characteristic of a Ring

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

\underbrace{1+...+1}_{\text{n summands}} = 0

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

\underbrace{a+...+a}_{\text{n summands}} = 0

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.

Irreducible Polynomials

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 F[x]

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 polynomial p(x) in F[x] can be factorized into polynomials that are irreducible over F.  This factorization is unique permutation of the factors and multiplication of the factors by constants from F

Polynomials over Finite Fields

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

p_5(x)=x^2+1\,=(x+1)^2

is not irreducible as it was over \mathbb{Z} or \mathbb{Q}.  This behavior occurs because finite fields have non-zero <characteristic

Generally,  if a polynomial factors over \mathbb{Z} 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 \mathbb{Z} 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

x4 + 1,

which is irreducible over \mathbb{Z} and \mathbb{Q} but factors into 4 linear factors or 2 quadratic factors mod any prime p

Primitive Polynomials

A primitive polynomial is the minimal polynomial of a primitive element of the extension field GF(pm).  In other words,  a polynomial F(X) with coefficients in GF(p) = Z/pZ is a primitive polynomial if it has a root α in GF(pm) such that \{0,1, \alpha, \alpha^2, \alpha^3,\dots,\alpha^{p^{m}-2}\} is the entire field GF(pm),  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

Properties of 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 mF(x) over GF(p) for prime p,  is a primitive polynomial if the smallest positive integer n such that F(x) divides xn - 1 is n = pm − 1. 

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

The roots of a primitive polynomial all have order pm − 1.

Generating Random Bits

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 2lfsr length) is related to a primitive polynomial.

For example,  given the primitive polynomial x10 + x3 + 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 210−1 = 1023 random bits. 

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


Last modified: 2008 FEB 14
bnostran@syr.edu