# Constructing Finite Field Tables

Could someone please walk me through how to construct Finite Field tables? My biggest confusion is how to get the elements from the respectable fields.

For example. I'm asked to construct the table with 8, 9, and 16 elements. My first thought is to take the elements and factor them as a product of primes: $2^3, 3^2, 2^4$ for each of the tables. However, I don't know how to come up with the polynomials.

Terras makes this statement in her book: "If $\alpha$ is a root of $f(x)$, the field obtained by adjoining $\alpha$ to $\mathbb{F}_p$ is $\mathbb{F}_q\cong \mathbb{F}_p[x]/f(x)$...Example: $\mathbb{F}_4\cong \mathbb{F}_2[x]/(x^2+x+1)=\mathbb{F}_2(\alpha)=\{0,1,\alpha,\alpha+1\}$"

How does she get that set of polynomials? Where does that polynomial that the cosets are formed from? For $\mathbb{F}_3$, what elements would I have in my set? I'm new to field theory, and this book makes a lot of jumps.

• The polynomial $f(x)$ has to be irreducible. You can use a version of the sieve of Eratosthenes to find the irreducible polynomials modulo $p$, for a prime number $p$. – Dustan Levenstein Mar 3 '16 at 17:41
• It's all the polynomials of degree less than $2$ (the degree of $x^2+x+1$) over $F_2$. – Thomas Andrews Mar 3 '16 at 17:41
• Thanks guys. Is it always the case that the polynomial has to have degree less than 2 over F2? So like for F3, then it would be polynomials of degree 2 or lower? – kingdras Mar 3 '16 at 18:37

To combine and maybe condense the content of the comments, let’s say this:

If you want a (the) field with $p^m$ elements, you start with the field $\Bbb F_p=\Bbb Z/p\Bbb Z$. For simplicity, let’s call this field $k$. Then you find and fix a monic poynomial $f(x)$ of degree $m$ that’s irreducible over $k$.

Now your elements of $\Bbb F_{p^m}$, I’ll call this bigger field $K$, may be represented as polynomials of degree less than $m$, say $a_0+a_1x+\cdots a_{m-1}x^{m-1}$, with coefficients in $k$. You add two of these things in the obvious way, but for multiplication, you do the standard obvious thing, but then take your product $P(x)$, and work Euclidean Division of Polynomials on it, by dividing by $f(x)$ and using now the remainder (necessarily of degree $<m$) instead of $P$.

Example: $p^m=9$, $k=\Bbb F_3$ with elements $\{0,1,2\}$. Since $-1=2$ is not a square there, you can use $x^2+1$ as your irreducible polynomial, and call your basic element now $i$ instead of $x$ — makes things very transparent. So now $(2+i)+(1+i)=2i$, but $(2+i)(1+i)=1$. Easy now to get the reciprocal of an element, too, same as in high-school. For higher degree than $2$, it’s a bit more of a pain to get reciprocal, but there are tricks that I won’t go into here.

• Thanks so much for the help, and to all others as well. I know I'm converging to a better understanding, but I have a few questions: 1. The cardinality of the set of elements will always be the same size as the prime in question? That is $p$ in $\mathbb{F}_p$? 2. You made the statement "Since $-1=2$ is not a square there..." what do you mean by not a square there? 3. Why do we need the recriprocal of the elements, and how does that translate to the elements needed to create the table? – kingdras Mar 4 '16 at 21:31
• The field with $q$ elements is conventionally written $\Bbb F_q$. And $-1$ is not a square in $\Bbb F_3$ because everything in that field has square $0$ or $1$. You need to calculate reciprocal of an element when you divide one element by another. It’s a field, after all. – Lubin Mar 4 '16 at 22:19
• Thank you. I may have to go back into Dummit and Foote and work some of the problems. I've had no treatment in fields whatsoever besides some of the information we've went over on the side in class, but Terras just jumps directly into Finite Fields, without any other information prior to it. I'm finding that a lot of time is spent searching through other books to make sure I have a firm understanding of all the middle steps. – kingdras Mar 5 '16 at 7:56
• That being said, thanks very much for helping me, and having patience. I don't know anything about fields, except the very basic axioms that constitutes a field and I'm not even sure what a field element is supposed to look like. Do you know of any good sources that would give me a good introduction to this? I think I'm OK on rings and ideals for now, but I would like to have a solid foundation in polynomials in rings and how they lead up to the types of fields represented as $\mathbb{Z}/p\mathbb{Z}$. – kingdras Mar 5 '16 at 7:58
• No, sorry, I guess I can’t help you with texts. I learned the bulk of this stuff from Lang as an undergraduate, and when I taught it, I rarely used a text either. Would go into Lang’s Algebra when I forgot a proof. But I do recommend doing lots of examples. And writing down all the nonzero elements of a finite field as powers of one well-chosen element. Then you have a “log-and-exponential” table to make multiplication much simpler, if you’re doing repetitive stuff. – Lubin Mar 5 '16 at 14:35

Let $\Bbb F_p$ be the finite field with $p$ elements. Given any irreducible polynomial $f(x) \in \Bbb F_p[x]$ the quotient $\Bbb F_p[x] / (f(x))$ is a field (since $f$ irreducible implies $(f(x))$ maximal). Now, for every polynomial $p(x) \in \Bbb F_p[x]$, its image in the projection $\pi:\Bbb F_p[x] \to \Bbb F_p[x] / (f(x))$ is equivalent to the remainder of the division of $p$ by $f$. So the only thing you need is an irreducible polynomial. From that you can build the multiplication table.

In the case you cited, $\alpha = \pi(x)$. Check that any $p(x) \in \Bbb F_2[x]$ is equivalent to an element of $\{0,1,\alpha,\alpha+1\}$ by dividing it by $x^2 +x + 1$ (observe that $\pi(x^2+x+1) = 0$, so $\alpha^2 +\alpha +1 = 0$)

• Indeed, all the above is true for any field $\mathbb F$. It's only when you start listing the polynomials of smaller degree that you need $\mathbb F$ finite. – Thomas Andrews Mar 3 '16 at 18:11
• OK, I believe I have at least a partial understanding. For the table with 9 elements in it, I would have $\mathbb{F}_9\cong \mathbb{F}_3/(f(x)=irreducible)=\mathbb{F}_3(\alpha)=\{0,1,\alpha,\alpha +1,\alpha^2,\alpha^2+1,\alpha^2+\alpha+1\}$. Is that how it works? @Vinicius, also, when you say dividing each element by $x^2+x+1$, you mean the element on top and the polynomial on the bottom right? Lastly, what about the cases with 8 elements and 16 elements? I'm not sure what my irreducible polynomial would be there? – kingdras Mar 3 '16 at 18:47
• @kingdras, no, this is wrong. I mean euclidean division, write $p$ as $p(x) = q(x)f(x)+r(x)$ with the degree of $r(x)$ lower than that of $f$. Consider the polynomial $f(x) = x^3+x+1$ over $\Bbb F_2$ and do the process I described. What is the image of an element of degree greater or equal to 3 by $\pi$? And smaller than 3? How many elements are in the image? – Vinicius M. Mar 3 '16 at 19:07
• So $f(x)=x^3+x+1$ would be the irreducible polynomial, and we can pick ANY irreducible polynomial. So then if I was to take the element 0 for example, then it would be $0=q(x)(x^3+x+1)+r(x)$ and so all possible elements would be $\{0,1, \alpha, \alpha+1, \alpha^2, \alpha^2+1, \alpha^2+\alpha+1\}$ that would show that it's irreducible? For the image of degree greater than or equal to 3 for $\pi$ would that be 0 since $f(x)$ is maximal? I'm sorry I'm still trying to wrap my head around all of this. – kingdras Mar 3 '16 at 19:47