Finite Fields
15-750, Spring 2001
D. Sleator

Outline
-------
Finite Fields
  Definition
  Polynomials of degree d have at most d roots, proof
  There exist finite fields of order p^m

Uses of finite fields:
  Constructing an nth root of unity for the FFT
  Data Dispersion
  Secret Sharing
  Error Correcting Codes

-----------------------------------

A _group_ is a set of elements G and an operation on them (+) with the
following properties:

  Associativity:    a+(b+c) = (a+b)+c  for all a,b,c in G.
  identity element: There is an element 0 in G such that
                    0+x = x+0 = x for all x in G
  inverse:          For any a in G there is an element -a in G
                    such that a+(-a) = 0;

Examples: 

(1) The integers modulo any number n under addition form a group.
    This is called Z_n.

This is obviously a group.

(2) The integers modulo any prime p (not including zero) under
    multiplicaion form a group.  This is called Z_p*.

Why is this a group?  All the properties are straightforward to verify
except the existance of inverses.  In this case the identity element
is 1.  Why does an inverse of an element a exist?  Consider the
sequence of numbers modulo p:

             a, 2a, 3a, 4a, .... (p-1)a

In this sequence, can the same number occur twice?  Say ia = ja
(modulo p) Then (i-j)a = 0 (modulo p).  This means that a(i-j) is a
multiple of p.  But since (i-j) < p and a < p, we know that (i-j) and
a cannot contain the prime p in their factorization.  Therefore a(i-j)
cannot be a multiple of p.  So we conclude the p-1 numbers in the
above sequence are all different.  Similarly 0 cannot occur in the
above sequence.  Since there are p-1 different numbers, from the
range 1...p-1, the the set of numbers is {1,2,4...p-1}.

A group is Abelian if the operation is commutative, that is
a+b = b+a for all a and b in G.  Both of the above groups are
Abelian. 

A _field_ is a set F of elements along with two operations (+ and .)
with the following properties:

   The elements of F under + are an Abelian group.
   (Let 0 be the identity for +.)
   The elements of F-{0} under . form an Abelian group.
   The distributive law holds:  For all a, b and c in F:
              a(b+c) = ab + ac

A _ring_ is like a field, only we don't require that multiplicaiton be
a group, and we don't require the multiplication be commutative
(unless it's a _commutative ring_).

The set of integers modulo p using modular addition and multipliation
and addition is a field.  We denote this field by Zp.

If n is of the form p^m (where p is prime) there exists a finite field
of n elements.  If n is not of that form, then there is no finite
field of n elements.  (For m=1 we've seen how to construct such a
field.  We'll see below how to do it for other values of m.)

First we prove a fundamental theorem that is crucial for all of our
applications of fields:

Root Theorem:
    Let P(x) be a non-zero polynomial of degree d over a field F.
    Then there are at most d roots of P (the solutions of P(x) = 0).

Proof:

Write the polynomial P() is written in normal form, that is, 
it looks like this:

               d            d-1             0
   P(x) = c_d x  + c_{d-1} x   + ... + c_0 x

This can be expanded around a point a, that is, write this as a
a polynomial where the monomials are powers of (x-a).  How do we do
this?  Let's give an inductive construction for doing this.

If the degree is 0, then it's easy.  Nothing needs to be done.  Assume
we can do it for all polynomials of degree d-1 or lower and prove it for
d.  So let P(x) = c_d x^d + Q(x), where Q is of degree d-1.
Let Q(x) = Q'(x-a) be the expansion of Q about (x-a).  What about the
high order term?

       d         d
      x  =  (x-a)  + R(x)

Where R(x) is a polynomial of degree d-1.  Now we can also rewrite 
R(x) as R'(x-a).  Combining these parts together gives:

                  d
  P(x) = c_d (x-a) + c_d R'(x-a) + Q'(x-a)

So, now we've written P(x) as an expansion around (x-a).  [Aside: that this
construction works over any ring (we have not made use of any properties
of a field).]

Ok, so back to proving our theorem.  Suppose we have a polynomial P() of
degree d.  We want to prove that P() has at most d roots.  Let's say a
is a root of P().  That is P(a) = 0.  Let's rewrite P(x) as P'(x-a).
We know that P(x) = P'(x-a) = 0.  Consider this last part.  It says:

                     d               d-1                 0
  P'(x-a) = b_d (x-a) + b_{d-1} (x-a)   + ... + b_0 (x-a)

Since P'(x-a) = 0, it follows that b_0=0, therefore we can factor
an (x-a) out of all terms and write this as:

  P(x) = P'(x-a) = (x-a) S(x-a).

Where S(x) is a polynomial of degree d-1.  (All we've done so far is
to show that if a is a root of a polynomial P() then we can factor P
into (x-a) times some polynomial of degree d-1.  This is the point of
all the stuff above.)

So we're interested in the roots of P(x) which are the roots of 
(x-a)S(x).  Well, if ab=0 in a field, then either a is 0 or b is 0 
(not true in a ring).  So any root of P(x) must be a root of (x-a)
or a root of S(x).  But  the degree of S(x) is d-1, so it has at most 
d-1 roots.  Therefore P(x) has at most d roots.

QED.

The way to construct a finite field with p^m elements (for m>1) is as
follows: We'll work with polynomials whose coefficients are elements
of Zp.  Specifically, the field we construct will be the set of
polynomials of degree < m.

First we find an "irreducible" polynomial P(x) in Zp of degree m.
That is, a polynomial that that cannot be factored over Zp.  Now our
field F of p^m elements will consist of all polynomials of degree < m
with coefficients taken from Zp.  Addition is defined in the obvious
way.  Multiplication is defined by multiplying the two polynomials in
the obvious way, then reducing the degree to be <m by applying the
identity P(x) = 0.

For example, say we want to construct a field of 4 elements.  Let p=2,
and m=2 use the polynomial x^2+x+1, which is irreducible.  Say a=x+1
and b=x.  Then

   a+b = 1
   ab  = (x+1)(x) = x^2+x = x+1+x = 1

We omit the proofs that this is a field, and that there exists
irreducible polynomials for any m.


Appliation 1: the FFT
----------------------

Our first application is to show how the FFT can be carried out under
a finite field.  So, for example, we can do convolutions of integer
vectors without resorting to complex numbers and floating point.

Actually, what we'll do is compute the convolution modulo a number b.
We'll choose b that's sufficiently large compared to the numbers we're
convolving so that no "wrapping" occurs.

Arithmetic modulo a number is a ring.  This ring must have the
following properties in order for the FFT to work:

 (1) w (omega) is a principle nth root of unity in the ring.
     (This just means that w^n=1, and no smaller power of w is 1).

 (2) n has a multiplicative inverse in the ring.

The latter is needed in order to be able to take inverses -- recall
that the inverse FFT needs a 1/n in front of it.

Given n (a power of 2) then any prime p of the form kn+1 can be used
as a modulus.  Under these conditions, the ring of integers (actually,
since p is prime, this is a field) modulo p has a principle nth root
of unity, and n has an inverse.  Since there are so many primes, it
turns out to be overwhelmingly likely that there is one of this form
that is O(n log n).

So, for the purpose of computing integer convolutions, we'll need a
prime that is greater than nb^2 of the form kn+1.  If we just start
looking at numbers of this form, we're likely to find one in log(nb^2)
tries, and its size will be roughly nb^2 + n log(nb^2).  This means
that only a few bits more than those required to represent nb^2 are
required to do this convolution.  It is a therefore very reasonable to
assume that arithmetic of this type can be done in constant time per
operation.

One more note.  Suppose we wish to take the non-cyclic convolution of
two vectors of length n, where n is not necessarily a power of 2.  We
can do this by doubling length of the vectors (and filling in the rest
of the entries with zeros).  Now we can round up to the next higher
power of 2, and use a cyclic convolution.  This is still O(n log n)
arithmetic operations.

Suppse we want to take the cyclic convolution of two vectors of
lengths that are not necessarily powers of two.  Then we can take
their non-cyclic convolution, and wrap the results modulo n at the
end.  This takes O(n log n) arithmetic operations.

Combining all of this together:

Theorem: For any n and any b, the convolution (both cyclic and
non-cyclic) of two vectors of length n can be computed modulo b in
time O(n log n), assuming that arithmetic on numbers of size
n(b^2+log(nb^2)) can be done in O(1) time.

It remains to show how, given n a power of 2, and a prime p as above,
to construct an appropriate w.  Let p = kn+1, where p is a prime, and
n is a power of 2 that we want to use for an FFT.  We need to show
that there is a principle nth root of unity, and we need to give an
efficient way to find it.

We'll make use of the root theorem shown above.

A principle nth root of unity is a number w such that
          n
         w  ~= 1    (I'll write ~= to mean "equivalent to modulo p")

and no smaller power of w is 1.

By Fermat's theorem, we know that for any a != 0, that

          p-1
         a   ~= 1

Note that p = nk+1.   We can write the above as:

     nk     k n 
    a   = (a )   ~= 1

So a^k is a candidate for an principal nth root of unity.
Let x = a^k.  Consider the following sequence:

     0   1   2   3   4   5        n-1
    x , x , x , x , x , x , .... x   

This repeats at x^n.  Because this is a field we can move backwards and
forwards in this sequence by multiplying by x^-1 or x.  So if a number
appears twice, that means the whole thing is periodic.  Does it repeat
sooner?  Well, if it's periodic.  The period must divide n.  n is a
power of 2, therefore the period is also a power of 2 and must divide
n/2.  Therefore x^(n/2) ~= 1.

Note that x^(n/2) must be a square root of 1.  There are only two square
roots of 1: 1 and -1.  We've just shown that this sequence has a repeat
in it then x^(n/2) ~= 1.  Therefore if x^(n/2) ~= -1, then the sequence
cannot repeat.  Thus in this case x is a principle nth root of unity.

Consider the equation

          kn/2
         x     ~=  1

This has at most kn/2 roots.  Similarly, 

          kn/2
         x     ~=  -1

has at most kn/2 roots.  But every non-zero element in the field
is a root of one of these or the other.  There are kn such
elements.  Therefore exactly half of them are solutions to the first
equation, and exactly half are solutions to the 2nd.  To find a
principle nth root of unity, just try a few numbers x chosen at
random.


Application 2: Data Dispersion
------------------------------

The rest of these applications are basically just taking advantage of
the root theorem.  For our purposes here, we can state the root
theorem as follows:

   If two polynomials A(x) and B(x) (of degree at most d) agree at
   d+1 points, then the polynomials must be the same.

This follows immediatley from applying the root theorem to the
polynomial C(x) = A(x)-B(x). 

This application arises from the design of a RAID system.

Suppose you have 2n bits of data that you want to store on 3 disk
drives, each of capacity n bits.  And you want it to be the case that
if any one of the disks dies, then you can recover all 2n bits of
data.  (In this model, when a disk dies, you know that it died.) 

This is easy.  Just take the bits of input data in pairs.  Store the
first bit on disk1, store the 2nd bit on disk2, and store the xor of
these two bits on disk3.  It's easy to see that any two of the disks
suffice to recover all the bits.

This parity construction works more generally.  Suppose you have kn
bits of data and k+1 disks, each of capacity n.  You divide the kn
bits evenly among the first k disks then store the parity of them on
the last disk.

But, how do we generalize this further.  Suppose you want the system
to survive if two disks die?  Suppose we have kn bits of data and k+2
disks of capacity n.  We could try to achieve this by dividing the
disks into two sets of k/2+1 disk each, and use one disk in each set
for a parity bit.  This works fine if up to one disk in each set
dies.  But fails if two in one of the sets die.

Here's how we solve this problem using finite fields.  We'll work over
a finite field F of order 2^b.  We take the kn bits of data and divide
them into blocks of k bytes each.  (As we'll see later if the byte has
b bits then we need 2^b >= k.)  These k bytes are then regarded as the
k coefficients of a degree k-1 polynomial over F.  Now pick k+2 points
0, 1, 2, ... k+1 at which to evaluate this polynomial.  Disk i stores
the result of evaluating this polynomial at point i.

Given any subset of size k of these values, there's just one
polynomial of degree k-1 that goes through all of them.  We can
compute the polynomial using Gaussian elimination.  [Yes, Gaussian
elimination works over finite fields.]

Of course this can be generalized to protect against any number of
failing disks.


Application 3: Secret Sharing
-----------------------------

This is a cryptographic application.  There's a secret key S.  There
are n participants, and we want to give each of them some data such
that any subset of them of size k can get together and construct the
secret S, but if any fewer of them get together, they cannot compute
any information about the secret S.

The technique is almost identical to the above application.  We
construct a finite field sufficiently large that the secret S is an
element of it.  Now we generate a random polynomial P() of degree k-1
with S as its constant coefficient.  Now we evaluate P() at 1, 2, 3,
... n and give each participant one of these values.  Clearly if any k
of them get together they can construct the whole polynomial P()
including S.  If fewer than that many get together, then there exists
a polynomial that is consistent with their values and all possible
values of S.

Application 4: Error Correcting Codes
-------------------------------------

In this problem we want to generate a set of vectors of some length l
(of elements from some finite field F or order n) such that if e
elements of the vector are corrupted, then we can still recover the
original vector.

Let d = l-2e.  We generate the set of all possible polynomials of
degree d-1.  (There are n^d of these.)  For each one we construct a
vector by evaluating that polynomial at l points, 0, 1, 2, 3, ... l-1.
Now, no two of these polynomials can agree at d points.

   No two of these vectors can agree at d components

   Any two vectors agree at <= d-1 components

   Any two vectors disagree at >= l-(d-1) components

   Any two vectors disagree at >= l-(l-2e-1) components

   Any two vectors disagree at >= 2e+1 components

Therefore if I change e components of one of the vectors, then
I'm still closer (Hamming distance) to the one I started at than any
other.  Thus I can correct e errors.

These are Reed Soloman codes.  A long sequence of refinements are
needed to convert this into a practical method.