5
$\begingroup$

I'm new to finite fields - I have been watching various lectures and reading about them, but I'm missing a step. I can understand what a group, ring field and prime field is, no problem.

But when we have a prime extension field, suddenly the elements are no longer numbers, they are polynomials. I'm sure there is some great mathematical tricks which show that we can (or must?) use polynomials to be able to satisfy the rules of a field within a prime extension field, but I haven't been able to find a coherent explanation of this step. People I have asked in person don't seen to know either, it's just assumed that that is the way it is.

So I have two questions:

What is a clear explanation of "why polynomials?".

Has anyone tried using constructs other than polynomials to satisfy the same field rules?

Thanks in advance.

$\endgroup$
  • $\begingroup$ Have you encountered the complex numbers before? Those are also usually expressed as polynomials in the variable $i$, with real coefficients. I think that the most important reason that we use polynomials is that that is usually how an extension is defined: A polynomial ring, divided out by some relation. $\endgroup$ – Arthur Jan 25 '16 at 8:01
  • $\begingroup$ Thanks - I've just started to look at complex numbers now, as every explanation of finite fields seems to mention them in passing. It hopefully will help! $\endgroup$ – Rene Wooller Jan 25 '16 at 12:06
4
$\begingroup$

In any ring, finite or infinite, we have two operations: $+$ and $\cdot$. The idea of a ring extension is this: let $R$ be a ring and $x$ be some element that we want to add to $R$ (maybe $R\subset S$ and $x\in S$, or $x$ is some formal element).

We need $R[x]$ to be closed under addition and multiplication.

This means that any element that can be formed by manipulating elements of the set $R\cup\{x\}$ by $+$ and $\cdot$ must be an element of $R[x]$.

Polynomials are a general way of expressing such manipulations.

An arbitrary polynomial in $x$ is a completely general manipulation of $x$ using only the operations valid in a ring. Moreover, any element of a ring can be expressed as a polynomial in terms of the generators of the ring.

Let's see how this works: start with some element $a\in R$. We can add or multiply by any other element of $R$, but this just gives us some $a'\in R$. Or we can multiply by $x$ any number of times to get $a'x^n$ for some $n$. And given different elements of this form, we can add them together to get a polynomial.

In many rings, because the elements $x$ satisfy non-trivial relations (e.g. in $\mathbb C=\mathbb R[i]$, $i^2+1=0$), there are neater ways to express elements, and we can avoid polynomials, even though they lurk in the background. In finite fields, polynomials happen to be the easiest and most intuitive way to express what's going on.

$\endgroup$
  • 2
    $\begingroup$ Ah, something clicked reading this - it's about having an element that is outside the original field, and attempting to add it to that field - which is basically what we must to do when we're dealing with a field that isn't prime. And because it's outside, it's convenient to call it x and that starts the whole concept of using a polynomial. There's a few other details I need to get but, that's helped, thanks. $\endgroup$ – Rene Wooller Jan 25 '16 at 12:11
6
$\begingroup$

The short answer is that you do not need to view the elements of finite fields as polynomials, but it simply is the most convenient presentation for many a purpose.


The slightly longer answer is that those elements really aren't polynomials, but instead they are cosets in a ring of polynomials, and we simply select the lowest degree polynomial to represent the entire coset. This version of the answer is pedagogically possibly the worst I'm gonna give, but it does come in handy when you do calculations in a finite field in a computer program. Namely, with a bit of care you can use either those low degree polynomials, or you can use monomials to represent the same elements. The former are useful for addition, the latter for multiplication. This is because we can use discrete logarithm tables. I'm not gonna discuss this aspect now, but if you are interested you can take a peek at this Q&A I prepared for referrals like this in mind.


Then the long answer - building up on the explanation given by Mathmo123 (+1).

When working with algebraic extensions of number fields, say $\Bbb{Q}$, students often take comfort in thinking of those extensions as consisting of some explicit numbers. Been there, done that. This works because we can always think of a copy of that extension field inside the field of complex numbers $\Bbb{C}$. This does have some pitfalls (there are often several distinct ways of view the given field as such a subset), but we can do this because A) $\Bbb{C}$ is algebraically closed, B) at that point in our studies the concept of a number is still closely tied to $\Bbb{C}$ and its subsets.

Consider the following. It is certainly more natural to work with $\sqrt2$ rather than the coset $x+\langle x^2-2\rangle$ in the quotient ring $\Bbb{Q}[x]/\langle x^2-2\rangle$. We easily do arithmetic as follows $$ (3+\sqrt2)(5+4\sqrt2)=15+(5+12)\sqrt2+4(\sqrt2)^2=23+17\sqrt2. $$ But notice that we multiplied those numbers involving $\sqrt2$ exactly like we would multiply the polynomials $$ (3+x)(5+4x)=15+17x+4x^2. $$ Only in the end we replaced $x^2$ with $2$. All because we think of $x$ having "value" $x=\sqrt2$. Saying that we here actually did arithmetic with polynomials modulo $x^2-2$ is just a fancy way of saying that we use $\sqrt2$ exactly as we use $x$ except in the end we replace all occurrences of $(\sqrt2)^2$ with $2$.

Building up on this we can similarly do arithmetic with $\root3\of2$. Only this time we can only simplify third powers and higher. So compare (I write $\root3\of 4$ in place of $(\root3\of2)^2$ and similarly for higher powers) $$ \begin{aligned} (1+2\root3\of2+3\root3\of4)(1+\root3\of4)&=1+2\root3\of2+(3+1)\root3\of4+2\root3\of8+3\root3\of{16}\\ &=(1+2\cdot2)+(2+3\cdot2)\root3\of2+4\root3\of4\\ &=5+8\root3\of2+4\root3\of4 \end{aligned} $$ replacing $\root3\of 8$ with $2$ and $\root3\of{16}$ with $2\root3\of2$ (and $\root3\of{32}$ with $2\root3\of4$ should the need arise). This is, again, exactly like working with polynomials $$ (1+2x+3x^2)(1+x^2)=1+2x+(3+1)x^2+2x^3+3x^4, $$ where this time we replaced $x^3$ with $2$ and $x^4$ with $2x$.

What's the deal you may ask? In these two example we could have simply used the real numbers $\sqrt2$ and $\root3\of2$. We might even have tried to use their decimal approximations to do the arithmetic with a pocket calculator. Sure, that would introduce rounding errors whereas doing it as above is precise, because it is easier to identify the numbers exactly. By this I mean, it is in this sense more informative to write $$ (\sqrt2-1)^{100}=94741125149636933417873079920900017937-66992092050551637663438906713182313 772 \sqrt{2} $$ instead of $$ (\sqrt2-1)^{100}=5.2775391806914391296141\cdot10^{-39}, $$ which is what a calculator might give you. For example, from that decimal expansion it is very hard to realize that it actually is a number of the form $a-b\sqrt2$ for some integers $a,b$.

Forward we go. What is you want to do arithmetic with the largest real zero of $x^5-2x^3-2x+2$. Plotting that polynomial shows that this number is slightly bigger than $1.5$. Well, this time we DO NOT HAVE A NICE EXPRESSION FOR THAT NUMBER IN TERMS OF RADICALS. So what to do? Just call the number $\alpha$, do arithmetic with its polynomials as above, and keep in mind that by the defining equation $$ \alpha^5=2\alpha^3+2\alpha-2. $$ Therefore we can calculate for example that $$ \begin{aligned} \alpha^7&=\alpha^2\alpha^5\\ &=\alpha^2(2\alpha^3+2\alpha-2)\\ &=2\alpha^5+2\alpha^3-2\alpha^2\\ &=2(2\alpha^3+2\alpha-2)+2\alpha^3-2\alpha^2\\ &=6\alpha^3-2\alpha^2+4\alpha-4. \end{aligned} $$

What has this got to do with doing arithmetic in finite fields? There the situation is much like in that last case. It is not convenient to use a numerical value for $\alpha$, when we need to do exact arithmetic and avoid rounding errors and such. All we have to work with is that polynomial equation satisfied by $\alpha$. We use that equation to do our arithmetic. The price we need to pay is that $\alpha$ does not have a precise identity. In the above example any of the five zeros of that polynomial - two of them complex numbers - would lead to the same arithmetic. This is because the related fields are isomorphic.


Enough of why polynomials (modulo an equation). You asked for alternatives. Let's look at the field of four elements, denote it $\Bbb{F}_4$ or $GF(4)$, whichever you are more familiar with. The field looks like $$ \Bbb{F}_4=\{0,1,\alpha,\alpha+1\}, $$ and its arithmetic follows from it having characteristic two (so $1+1=0=\alpha+\alpha$) and the special equation $\alpha^2=\alpha+1$.

We can produce $\Bbb{F}_4$ as a quotient ring much the same way that we produce the field of seven elements as $\Bbb{Z}/7\Bbb{Z}$ - residue classes of integers modulo seven. Here's one way. Let $\omega=(-1+i\sqrt3)/2$ be the usual complex primitive third root of unity. Let us look at the ring $$ \Bbb{Z}[\omega]=\{a+b\omega\mid a,b\in\Bbb{Z}\}. $$ We can then reduce modulo two in the ring $\Bbb{Z}[\omega]$. In other words, we can do arithmetic as usual, but do operations with $a,b$ modulo two, so effectively both $a$ and $b$ will have two choices, $0,1$, and we have four combinations of them altogether. What do we get? Because $$ 0=\omega^3-1=(\omega-1)(\omega^2+\omega+1) $$ we can deduce that $$ \omega^2=-\omega-1. $$ Now, if we reduce this modulo two, we see that, because $1\equiv-1\pmod2$, $\omega^2=\omega+1$. In other words $\omega$, or more precisely, its residue class modulo two, takes the role of $\alpha$ in $\Bbb{F}_4$

We can produce any finite field in this way. In infinitely many different ways. But using the resulting representations of complicated numbers with coefficients modulo a prime number does not really help us to do any arithmetic operations. So we just usually won't bother.


This became even longer than I anticipated. Hope it helps :-)

$\endgroup$
  • $\begingroup$ There was an arithmetical error. Should be ok now. $\endgroup$ – Jyrki Lahtonen Jan 25 '16 at 11:35
  • 1
    $\begingroup$ this answer is great too - thanks. I need to study it a bit longer though :-D $\endgroup$ – Rene Wooller Jan 25 '16 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.