Thread: Galois fields

Hello everybody,
i just started studying coding theory from the book "error control coding" by lin and costello. In the 2nd chapter he has given a brief overview of the galois fields. No there are a few confusion that i have and i would be thankful to whoever can help me calrify them.

1. While defining a field (or a group) it sometimes seems to me that you can define addition and multiplication whatever way u want it . like sometimes its modulo m where m is the size of the finite field or group sometimes its polynomial addition etc. so please kindly can somebody explain what are the restriction on how we define these binary operators.

2. Now it was mentioned in the book that galois fields (considering modulo addition and modulo multiplication) exist for size p^k where p is a prime and k is a
positive integer. Why?. i tried to construct for a couple of non primes but the table for multiplication doesn't come out right.

3. What is the Significance of the characteristic of a field.

4. I have read two different definitions of irreducible polynomials over GF(q). One says that a polynomial is irreducible over GF(q) if it doesn't have any root in GF(q). Second one which i read in the above mentioned book and which I am not sure if it holds in general of only for GF(2^k) says that a polynomial of degree n over Gf(q) is irreducible if no polynomial over GF(q) of degree less than n and greater than 0 is a factor of it. So are the two equivalent if yes how and if no so whcih one is right or more general.

5.Can somebody explain to me comprehensively the procedure of extending a finite field. I have an idea abt it but there are a lot of confusions so rather than posting all of them may be a brief idea by someone can help me better.

6. if i use different irreducible polynomials of the same degree m to extend a field GF(p) i will get different fields of the same size??


thanks in anticipation

1. no. the operations of addition and multiplication on a field are quite restrictive:

addition must be associative and commutative. there must be an additive identity (usually called 0), and every element must have an additive inverse (usually written as -a, for a given element a).

multiplication must also be associative and commutative. there must be a multiplicative identity (usually called "1" or "unity"), and every element except 0 must possess a multiplicative inverse (often written 1/a, for a given element a, but also sometimes as a^-1).

furthermore, multiplication MUST distribute over addition:

a(b+c) = ab + ac.

this ensures that multiplication and addition are "compatible" (in other words, you can't take just "any two" associative and commutative binary operations, and "put them together" and get a field. they have to interact with each other in a certain way).

the purpose for these rules is so that we can do algebra in fields, and the same rules learned in elementary school (for the most part) still work (but see the discussion on characteristic below).

2. the reason that finite fields, in general, do not exist for numbers that are not powers of a prime has to do with the peculiarities of multiplication in the integers mod n. for example, in Z₆, we have (2)(3) = 0, but neither 2 nor 3 is 0. so suppose we were looking for some k (mod 6) with 2k = 1 (that is, a multiplicative inverse).

2(0) = 0 that doesn't work (of course, we wouldn't expect 0 to have an inverse, anyway).
2(1) = 1, nope.
2(2) = 4, try again.
2(3) = 0, can you guess what happens next? we're not going to get any new numbers, we're going to get the cycle (0,1,4) again. why? because of the distributive law:

2(4) = 2(3+1) = 2(3) + 2(1) = 0 + 1 = 1 (told ya)
2(5) = 2(3+2) = 2(3) + 2(2) = 0 + 4 = 4.

a number like 2 or 3 in Z₆ is called a "zero-divisor". if we have zero-divisors, they act "bad" (with respect to division) just like 0 does. in a field (or more generally, even in an integral domain like the integers), if:

ab = 0, we know straight-away that one of a or b must be 0.

when we have zero divisors, all bets are off. anything that has zero-divisors cannot be made into a field. it turns out that in Z_n, a is a zero divisor if and only if gcd(a,n) ≠ 1. so if we want to make Z_n into a field, n can't have any divisors except 1 and itself (different than 1, for slightly technical reasons). we call those kind of numbers prime.

3. in any field, we have 1. so we can form 1+1,1+1+1,1+1+1+1, etc. if all of these are different, we say F has characteristic 0. if some sum of 1's is equal to 0:

1 + 1 +...+ 1 = 0 (where we have n 1's)

we say that F is of characteristic n. but the collection of sums of 1 (and 0, if 0 isn't one of them) is either isomorphic to Z_n, or N. if it's N (the natural numbers), we know that (since we have additive inverses) we have a copy of Z in our field. and since we have multiplicative inverses, we have a copy of Q in our field (Q is what you get when you take all the inverses of integers, 1/k, and start adding them together).

but if F is FINITE, we have a copy of Z_n in our field. and since we DON'T have zero divisors in a field, n has to be prime:

any finite field is of prime characteristic (since every sum of 1's has to have an inverse, so we can't have any (non-trivial) divisors of n).

so, you might wonder, where do we get fields of prime power order?

well, it runs out that if F is a field, and E is a field that contains F inside it, that we can regard E as an F-vector space. if E is finite, then it must be finite-dimensional over F. but any two vector spaces over a common field F of the same dimension, are isomorphic (as vector spaces). so if dim_F(E) = n, then E is isomorphic to Fⁿ =

{(a₁,a₂,...,a_n) : a_k in F}, consisting of n-tuples of elements of F.

in particular, since E and Fⁿ are isomorphic (as vector spaces), they have the same size!!!!

now the smallest field that contains all the sums of 1, is called the prime field of E. we saw above that the prime field of a finite field has to be Z_p, for some prime p. so if E is finite, then E is isomorphic to (Z_p)ⁿ, for some prime p. but we know the size of (Z_p)ⁿ, we have p choices for each coordinate, and n coordinates in all, giving us pⁿ elements in all in E.

so the only "possible sizes" are powers of prime numbers. it turns out (and here i am going back to your 2nd question) that every "possible size" does indeed occur, and even better, that for all intents and purposes, there is only "one" finite field of a given size (this is in stark contrast to the situation for infinite fields, where two extensions of Q may be "the same size" (of degree 2 over Q as vector spaces), but be non-isomorphic).

4. the first criterion you give is clearly incorrect. for example: x⁴ + x² + 1 has no roots in GF(2) (which has only two elements, 0 and 1, and you can check that neither is a root), but x⁴ + x² + 1 = (x² + x + 1)² is reducible over GF(2). it is true that for polynomials of degree 3 or less that they are irreducible if and only if they don't have a root, but that is because if they do factor, one of the factors must be linear (of the form x - r, where r is a root). we don't count factors of degree 0 (non-zero constants), because those are invertible (since we're in a field). otherwise, EVERYTHING would factor as:

f(x) = (a)(1/a)f(x), which is just silly.

5. the general idea is this (bear with me, this will take a while): we start with our field F. then we create the RING F[x], of polynomials in x with coefficients in F. now to really understand what we do next, you have to know a little bit about rings.

rings are pretty much like fields, except we might not be able to divide. also, ring multiplication isn't always commutative, and rings don't always have "unity" (something like 1). fortunately for us, the ring F[x] IS commutative: p(x)q(x) = q(x)p(x), which makes our lives a lot easier. also, the polynomial f(x) = 1 (a constant polynomial, whose constant term is 1) is a multiplicative identity, so that helps out, as well. now, we could make F[x] into a field using the same method we used to make fractions from integers, but instead, we're going to do something else (F[x] is infinite, and we want a finite field with F inside it, making "polynomial fractions" would give us something "even bigger" than F[x], and that's not what we're after).

to understand it, you have to know what an ideal of a ring is. basically, an ideal is something (a subset of a ring) that mimics the following properties of 0:

0 + 0 = 0
a0 = 0.

given a ring R, we define an ideal to be:

a subset I, such that I is closed under addition and contains additive inverses and 0, and such that if r is any element of R, and a is any element of I, ra, and ar are both in I.

(since "our ring" F[x] is commutative, we only have to check that ra is in I, since ra = ar).

now given a ring R, and an ideal I, we can create a "smaller ring", called R/I, in the following way:

we define a + I to be the set {a + x: x in I}. this is called the coset of a in R/I. intuitively, we imagine that "all the elements of I are set to 0".

we define addition of cosets as:

(a + I) + (b + I) = (a+b) + I

but there's a slight hitch: a+I is a set (as are b+I and (a+b)+I), whereas a,b and a+b are elements of R. so we want to make sure that the sum doesn't depend on our choice of a and b (as "representatives" of the coset).

that is: if a' is in a+I, and b' is in b+I, we want to be sure that a'+b' is in (a+b)+I. so what does it mean for a' to be in a+I?

well, if a' is in a+I, then a' = a+x, for some x in I. similarly, if b' is in b+I, then b' = b+y, for some (other) element y of I. so:

a'+b' = a+x+b+y = (a+b)+(x+y). but one of our conditions on I was that it be closed under addition, so if x is in I, and y is in I, then x+y is in I. thus a'+b' = a+b+(x+y), for some element x+y in I, so a'+b' is indeed in (a+b)+I.

we define multiplication of cosets like so:

(a+I)(b+I) = ab+I

again, we need to check this doesn't depend on our choice of a or b.

so if a' is in a+I, and b' is in b+I, then a' = a+x, and b' = b+y, for some x,y in I.

a'b' = (a+x)(b+y) = ab + ay + bx + xy. now the other condition on I was that if x is in I, then so is rx, for any element r of R. so ay,bx and xy are all in I. but then, so is their sum, so

a'b' = ab + (ay+bx+xy), for some ay+bx+xy in I, that is, a'b' is in ab+I.

so we get a ring, except 0 is now replaced by the "larger" 0+I = I. it turns out that the mapping R→R/I given by a→(a+I), preserves the addition and multiplication of R (it is a ring-homomorphism). it also turns out that the set {r in R: r+I = I} the KERNEL of this homomorphism, is just I. it also turns out, that if we have ANY ring homomorphism φ:R→S, between a ring R and another ring S, that ker(φ) is an ideal of R, and that R/ker(φ) is "essentially the same" (isomorphic to) φ(R) (the image of R in S).

it also turns out that, given a polynomial p(x) in F[x], that the set {k(x) in F[x]: k(x) = g(x)p(x)} is an ideal of F[x], called the ideal generated by p(x), or <p(x)>. so for any polynomial, we can form the ring F[x]/<p(x)>.

now, we have the following important result:

suppose R is a commutative ring with identity, and M an ideal of R. then R/M is a field if and only if there is no ideal between M and R (such an ideal is called maximal).

suppose R/M is a field. let I be an ideal such that M is a proper subset of I. pick a such that a is in I, but not in M. since 0 is in M, a is not 0. thus there is b+M in R/M such that:

(a+M)(b+M) = 1+M. this means that 1 = ab+m, for some m in M. now ab is in I (since a is in I, and I is an ideal), and m is in I, (since M is a subset of I), thus 1 = ab+m is in I. but this means that every element r = r1 is in I, so I = R: any ideal containing M must be the entire ring R.

on the other hand, suppose M is a maximal ideal. let a+M be a non-zero element of R/M ( that is, a is not in M). we need to show there is some b+M with (a+M)(b+M) = 1+M. to do so, we are going to take what may seem like an odd detour:

let M' = {ra + s : r in R, s in M}. clearly M' contains M as a subset (let r = 0), and it also contains a (since we can take s = 0, since 0 is in M, and r = 1), so it is strictly bigger than M. i claim M' is an ideal of R:

(ra + s) + (r'a + s) = (r+r')a + (s+s'), so M' is closed under addition. -(ra + s) = (-r)a + (-s), which is in M' since -s is in M, and -r is an element of R. thus M' contains additive inverses, and it clearly contains 0 (since 0 is in M, and M' contains M). now suppose t is any element of R. then t(ra + s) = (tr)a + ts, and ts is in M (since M is an ideal), and tr is clearly in R. thus M' is an ideal of R.

but...since M is a maximal ideal, M' must therefore be all of R. in particular, 1 is in M', that is 1 = ba + s, for some b in R, and s in M. since R is commutative, we can write this as:

1 = ab + s (since ab = ba). this means that 1 is in ab+M, that is: 1+M = ab+M. hence (a+M)(b+M) = ab+M = 1+M, so for any non-zero a+M in R/M, we have a multplicative inverse, b+M.

well.

so the natural question is, at this point, for which polynomials p(x) is the ideal <p(x)> maximal? well, if q(x) is a factor of p(x), then <p(x)> is contained in <q(x)>, so if <p(x)> is maximal, p(x) has to be irreducible. on the other hand, suppose that p(x) is irreducible, but <p(x)> is not maximal. so we must have some ideal I (strictly) between <p(x)> and F[x].

now any such ideal will be of the form <f(x)> for some polynomial f(x). why? well, suppose some ideal J of F[x] has a non-zero element in it. let g(x) be an element of minimal degree in J. for any k(x) in J, we can write k(x) = q(x)g(x) + r(x), where deg(r(x)) < deg(g(x)), or r(x) is the 0-polynomial. then r(x) = k(x) - q(x)g(x), which is in J. since g has minimal degree in J, it must be that r(x) = 0, so every k(x) in J is of the form q(x)g(x), that is: J = <g(x)>. note that any non-zero element of F generates all of F[x], since for b ≠ 0 in F, (1/b)b = 1 is in <b>, so that all of F[x] is in <b>.

but if <p(x)> is contained in <f(x)>, then p(x) is in <f(x)>, so that p(x) = h(x)f(x), for some h(x) in F[x]. thus either 0 < deg(f(x)) < deg(p(x)), contradicting the irreducibility of p(x), or h(x) is a constant polynomial, so that h(x) = c, in which case f(x) = (1/c)p(x) is in <p(x)>, contradicting that I (= <f(x)>) is an ideal (strictly) between <p(x)> and R.

so the conclusion is: <p(x)> is maximal if and only if p(x) is irreducible in F[x].

and THAT means, that if p(x) IS irreducible over F, that F[x]/<p(x)> is a field. and this field includes (a copy of) F inside it:

for any a in F, the map a→(a+<p(x)>) embeds F inside F[x]/<p(x)> (it's a ring-isomorphism), we have succeeded in making an "extension" of F.

********

now, that's a lot to take in...but in point of fact, that's how it's done.

thanks ...i haven't read your complete answer yet but hopefully by tomorrow i will have done it...thanks