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