# Convert polynomials and fractions in a finit field?

I am trying to understand how finite field works, and I am stuck on converting high power polynomials into a power of the field, also converting fractions into integers.

1. $8^{-1}\cdot44$ in $\Bbb F_{101}$ (the answer is 56 mod 101) I am not too sure how it got there
2. $x^4$ in $\Bbb F_{\large 2^3}$

any enlightenment would be much appreciated!

• Do you understand what $8^{-1}$ is? – Git Gud Apr 3 '13 at 20:46
• Only if you understand what $44/8$ is. – Git Gud Apr 3 '13 at 20:48
• Polynomials over finite fields work exactly the way they normally do; that is, just because $$a^p=a$$ for any $a\in\mathbb{F}_p$ does not mean that the polynomials $x^p$ and $x$ are equal as elements of $\mathbb{F}_p[x]$. Thus, in your second question, there is nothing to do. – Zev Chonoles Apr 3 '13 at 20:49
• @Yonk $8^{-1}$ is just shorthand notation for the only element $x$ of your field such that $8x=1$. – Git Gud Apr 3 '13 at 20:50
• @Yonk You don't know what $8^{-1}\cdot 44$ is and you want to find what it is. Call it $a$. So $8^{-1}\cdot 44\equiv a \pmod {101}$. Multiply by $8$ on both sides to get something equivalent which you should be able to solve. – Git Gud Apr 3 '13 at 21:01

You have seen answers for the first question. For the second question:

The answer won't be unique. To construct a field of order $p^n$ for a prime $p$ you consider the polynomial ring $F_p[x]$ and a monic ireducible polynomial $f$ of degree $n$. Here $p=2$ and $n=3$.

Note that a polynomial of degree $3$ is reducible if and only if it has a zero. Hence we want a monic polynomial of degree $3$ in $F_2[x]$ with no zeros. It will be of the form

$$f(x)=x^3+ax^2+bx+c$$

where $a,b,c\in F_2$. Now $0$ shan't be a zero, so $c=1$. Then $1$ shan't be a zero as well so $(a,b)=(1,0)$ or $(a,b)=(0,1)$.

We end up with two options

$$f(x)=x^3+x^2+1$$ or $$g(x)=x^3+x+1$$.

In $F_2[x]/f$ we have $x^4=x\cdot x^3=x(x^2+1)=x^3+x=x^2+x+1$.

In $F_2[x]/g$ we have $x^4=x\cdot x^3=x(x+1)=x^2+x$.

You see that the answer is not unique.

• precisely what I was looking for, much appreciated! – Bonk Apr 4 '13 at 11:07
• @YonkShi: You might have gotten helpful answers sooner, if you had asked for this. Normally people denote by $x$ a variable, an indeterminate. You, OTOH, used it as a specific element of the finite field of 8 elements, i.e. a constant (=coset of $x$). Mind you, newcomers to the area often make this mistake, so don't worry. But you would benefit learning about quotient rings before you tackle finite fields. – Jyrki Lahtonen Apr 5 '13 at 6:59

$8^{-1}\cdot 44 = 2^{-1}\cdot 4^{-1}\cdot 4\cdot 11=2^{-1}\cdot 11$. Noting that $2\cdot 51=1$, we see that this is $51\cdot 11=561=56$.

As polynomial $x^4\in F_8[X]$ is just that - $x^4$. However, interpreted as $function$ from $F_8$ to itself, the answer may differ / the expression be rewritten. Is it the latter you are spposed to do?

• I'm afraid that "-" before that $\,x^4\,$ may induce the OP to believe that's a minus sign...perhaps ":" would be better? – DonAntonio Apr 3 '13 at 21:32
• Does the OP really mean $x^4\in F_8[x]$ or rather $x^4\in F_8\cong F_2[x]/f(x)$? Then $x^4$ would be equivalent to sth of a lower degree. It won't be unique, but maybe there is some convention (s)he isn't telling us about. – Simon Markett Apr 3 '13 at 21:51
• @Yonk Shi, maybe you want to comment on that. – Simon Markett Apr 3 '13 at 21:52
• @SimonMarkett Sorry I just saw your message. Yes, I think Hagen mistunderstood me. $F_{2^3}$ means a field $F_{2}$ but with a maximum degree of 3 in that field. Thus $x^4$ is out of that bound, it needs to be mapped down to something like $x^2+x$ – Bonk Apr 4 '13 at 9:20