Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Constructing a field of 4 elements

  1. Feb 26, 2015 #1
    This is from an example in my textbook:

    "The polynomial x^2+x+1 has no root in Z mod 2, and so is irreducible. Hence the required field is:

    F = Z_2[x] / <x^2 + x + 1> = {a + bt | a,b are elements of Z_2; t^2+t+1 = 0}.

    Thus F = {0, 1, t, 1+t} and t^2 = t + 1."

    I have two questions.
    My first question is if this a exercise problem rather than an example, I would have had no idea to grab the polynomial x^2+x+1 in Z mod 2. Can somebody explain why this was apparently so obvious?

    My next question is why is t^2 = t + 1? Wouldn't t^2 = -t - 1?
     
  2. jcsd
  3. Feb 26, 2015 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    t+1=-t-1 (mod 2)?
     
  4. Feb 27, 2015 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well, to obtain a field of ##p^n## elements, you want to quotient ##\mathbb{F}_p[X]## by an irreducible polynomial of degree ##n##. I assume that's clear and you're really asking how to find such a polynomial. Well, that is actually a hard question and a topic of research. It has been proven (and the proof is not trivial!) that such a polynomial always exists. But the proof doesn't really give a hint on how to find it. So what you could always do is check all cases. With low degree polynomials this is not hard. For example, you list all the second degree polynomials:

    [tex]X^2,~X^2 + 1,~X^2+X,~X^2 + X + 1[/tex]

    and you check whether they are irreducible. Only the last one is, so that's your polynomial. You can do the same with third degree, fourth degree, etc. To get beyond that is going to be difficult by hand. So you can always consult a computer algebra system like GAP http://www.gap-system.org Currently, people have also collected giant lists of irreducible polynomials, as no clever algorithm exists.
     
  5. Feb 28, 2015 #4
    The number of degree-n irreducible polynomials for GF(p) is given by
    $$ \frac{1}{n} \sum_{m \text{ div } n} \mu(n/m) p^m $$
    where μ is the Moebius mu function: 0 if n has repeated prime factors, (-1)^(number of factors) if those factors are all unique.

    That number gets big *very* quickly with increasing n; it tends to pn/n. For GF(2): A001037 - OEIS
     
  6. Mar 2, 2015 #5

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    the usual way to proceed to prove existence of such a field, is to use the fact that the multiplicative group of such a field is cyclic, hence if q = p^n, the elements of the field all satisfy the polynomial X^q - X = 0. Conversely it is not hard to show that in any splitting field for that polynomial, the set of all its q (necessarily distinct) roots forms a field. see van der waerden's modern algebra, chapter 5 section 37. I don't know if this is as explicit as what you want, since your discussion goes along the lines of finding the minimal polynomial for a primitive element for this splitting field extension. This seems however like a fairly elementary proof of existence of such a field and hence of such a polynomial.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook