I'm interested in getting to know a bit more about coding theory, so I've been studying a bit about finite fields. I haven't been able to understand how the following topics work:
- If we have a field $\mathbb{F}_p$ ($p$ is prime), we can use an irreducible polynomial (irreducible in $\mathbb{F}_p[x]$) $f$ of positive degree $n$ to generate an extension field $\mathbb{F}_q$, where $q = p^n$.
- We can also use that very polynomial to provide unique representations of the elements in $\mathbb{F}_q$.
I'm not really trained in maths, so simpler explanations are very welcome. Also, examples are very much appreciated.
Thanks in advance!
Best Answer
The idea is that if you have a polynomial $q(x)$ which is irreducible you can take $y$ to be one of the roots of the polynomial so that $q(y)=0$
Let's take $q(x)=x^3+x+1$ and suppose that $p=5$ to make it concrete. Note that this polynomial has no roots modulo $5$ - so being a cubic polynomial without a root, it is irreducible. And simply assume that there is a $y$ with $q(y)=0$.
What happens when we look at expressions involving the elements of $\mathbb F_5$, which we can call $0,1,2,3,4$ and $y$ - well we get polynomials involving $y$ with coefficients chosen from the field. And then we can divide one polynomial by another.
In theory the degree of these polynomials can be as large as you like. But notice that because $y^3+y+1=0$ or $y^3=4y+4$ (modulo $5$ remember) whenever we have a term of degree greater than $2$ in $y$ we can fund an equivalent polynomial of degree at most $2$ (just substitute for $y^3$ until you are done - there are easier ways, but this is the easiest way to see it is true).
So the expressions in $y$ that we get are $ay^2+by+c$. And how many do we get, well there are five possibilities for $a$, five for $b$ and five for $c$ so that gives $125=5^3$ elements.
It is quite obvious that we can add and multiply these, but what happens when we divide one polynomial by another? Well we can't divide by a multiple of $q(y)$, because this is zero by assumption. But if $r(x)$ is not divisible by $q(x)$ it turns out that there are polynomials such that $$r(x)s(x)+q(x)t(x)=1$$ and substituting in $y$ gives is $s(y)=\frac 1{r(y)}$ so that dividing by $r(y)$ is the same as multiplying by $s(y)$.
This is proved using the Euclidean algorithm for polynomials - it works the same way as for coprime integers, if you know it.
So we have arithmetic with all the familiar properties.
Just to show one example, what is $\frac 1y$ in the example case?
Well $y^3+y=4$ so that $4y^3+4y=1$ and $\frac 1y=4y^2+4$
($4\times 4 = 16\equiv 1 \bmod 5$)
And that is probably what you need to know to get hold of the basics. You can see how the polynomial functions to enable us to write expressions in the larger context.
To be a little more explicit, if we take expressions $ay^2+by+c$ with $a=b=0$ we find we have five elements $0,1,2,3,4$ which behave just like the field $\mathbb F_5$ that we started with. Because this field is concealed within the larger one, we call the larger one an extension. Because every expression is made up of (at most) three terms, it is of degree $3$ - the elements $1, y, y^2$ can be regarded as a basis of the larger field with coefficients in the smaller one (technically we have a vector space of dimension $3$ - but because we can multiply and divide, there is more structure than that).
The proofs that all this works in the general case belong to field theory - the role of $p$ being a prime and the polynomial being irreducible then become clear (really this is to make sure that division always works when you need it). The existence of a suitable $y$, which we assumed, can also be shown to be justified.