1
$\begingroup$

I am dealing with finite fields and somehow got stuck. The construction of a prime field $GF(p), p \in \mathbb{P}$ is pretty easy because every operation is modulo p. In other words $GF(p)$ contains all integers ranging from 0 to $p-1$.

However, non prime fields are a bit trickier. Given the power $q = p^n$ with $p \in \mathbb{P}$ and $n \in \mathbb{N}$, one has to find an irreducable polynom g(x) of degree n. Then the construction of $GF(p^n)$ is the following:

$GF(p^n) = \frac{GF(p)[x]}{g}$

Theoretically I get along with this definition. Unfortunately I fail to construct addition and multiplication tables for any GF(q). Though I can easily find the wanted table on the internet, I have not found an explication yet that really made me understand.

I would like to know how to create the addition and multiplication table for $GF(2^2)$ with the above knowledge. $GF(2^2)$ contains four elements. Let's call them $\{0,1, \alpha, \beta \}$. $g$ must be $x^2 + x + 1$ as there no other irreducable polynom of degree 2. So far I am able to construct the addition table partly (question marks indicating despair...):

| + | 0 1 $\alpha$ $\beta$ |

0 | 0 1 $\alpha$ $\beta$ |

1 | 1 0 ? ? |

$\alpha$ | $\alpha$ ? ? ? |

$\beta$ | $\beta$ ? ? ? |

I don't understand how to calculate for example $1+\alpha$. The result is $\beta$, but I don't know why. Concerning the above short explanation, I have to divide $1+\alpha$ by $g$. But how can I do this?

Thanks for your help

$\endgroup$
3
  • $\begingroup$ You're forgetting a very important part of the construction: $$\alpha = X \\ \beta = X+1$$ $\endgroup$
    – AlexR
    May 25, 2015 at 21:27
  • $\begingroup$ Our site search function leaves a few things to be desired, but if you use the string GF(4), the first hit it offers is this question. Does that help? Once you get the hang of using the polynomial $g$ things become a lot easier. I prepared this Q&A pair partly with referrals like this in mind. $\endgroup$ May 26, 2015 at 5:08
  • $\begingroup$ What is the relationship between those polynomials and $\alpha$, $\beta$? How do I create them? $\endgroup$
    – null
    May 26, 2015 at 14:06

1 Answer 1

1
$\begingroup$

This case is fairly easy because all the calculations are modulo 2 and the field has only 4 elements. Let $\alpha$ be a root of $g$, i.e, $\alpha^2 + \alpha + 1 = 0$. This immediately implies that $1+\alpha = -\alpha^2 = \alpha^2$, which you are calling $\beta$. I would suggest to try a polynomial of higher degree so that the field has more elements.

$\endgroup$
2
  • $\begingroup$ Why are all calculations modulo 2? $p$ in $GF(p) = GF(2^2)$ is not prime and therefore you should divide by the irreducible polynom (see above). $\endgroup$
    – null
    May 26, 2015 at 14:07
  • $\begingroup$ I meant operations on the prime field, which in this case is $\{0,1\}$. So basically you have to deal only with $\alpha$ and $\beta = 1+\alpha$. Then $\alpha + \beta = 1+2\alpha = 1$. $\endgroup$
    – user 1987
    May 26, 2015 at 14: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.