1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Do you understand what $8^{-1}$ is? $\endgroup$ – Git Gud Apr 3 '13 at 20:46
  • 3
    $\begingroup$ Only if you understand what $44/8$ is. $\endgroup$ – Git Gud Apr 3 '13 at 20:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Zev Chonoles Apr 3 '13 at 20:49
  • 2
    $\begingroup$ @Yonk $8^{-1}$ is just shorthand notation for the only element $x$ of your field such that $8x=1$. $\endgroup$ – Git Gud Apr 3 '13 at 20:50
  • 2
    $\begingroup$ @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. $\endgroup$ – Git Gud Apr 3 '13 at 21:01
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ precisely what I was looking for, much appreciated! $\endgroup$ – Bonk Apr 4 '13 at 11:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Apr 5 '13 at 6:59
2
$\begingroup$

$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?

$\endgroup$
  • 2
    $\begingroup$ I'm afraid that "-" before that $\,x^4\,$ may induce the OP to believe that's a minus sign...perhaps ":" would be better? $\endgroup$ – DonAntonio Apr 3 '13 at 21:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Simon Markett Apr 3 '13 at 21:51
  • $\begingroup$ @Yonk Shi, maybe you want to comment on that. $\endgroup$ – Simon Markett Apr 3 '13 at 21:52
  • $\begingroup$ @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$ $\endgroup$ – Bonk Apr 4 '13 at 9:20

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.