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.