0

I have read methods to construct GF(p^m). I have understood the primitive polynomials and other concepts but I have not understood how the p and m are entering into the discussion. And finally the proof the pudding. What are the elements of it, what are the two operations on this set? How do we show that they satisfy the requirements of a field? For simplicity let us take GF(3^2 =9). What are the elements of this field and what are the operations on this?

Seetha Rama Raju Sanapala
  • 339
  • 2
    Pick any irreducible polynomial $f$ of degree $2$ with coefficients in $\Bbb{Z}/3 \Bbb{Z}$. Then $GF(9) = (\Bbb{Z}/3 \Bbb{Z})[x] /(f) $. For example, you can take $f=x^2+1$. – Crostul Mar 22 '16 at 09:21
  • I know irreducible polynomials of degree 2 but rest of the answer I did not understand. Can it not be simplified further? Giving the 9 elements and the two operations on them? – Seetha Rama Raju Sanapala Mar 22 '16 at 09:30

3 Answers3

2

$$GF(9)=:\Bbb F_9=\Bbb F_3[x]/\langle\,x^2+1\,\rangle$$

and the elements of the quotient ring can be expressed in the form $\;aw+b\;,\;\;a,b\in\Bbb F_3\;,\;\;w^2=-1\;$ , so we actually get nine elements.

The fact $\;\Bbb F_9\;$ is a field is because $\;x^2+1\in\Bbb F_3[x]\;$ is irreducible , so the ideal generated by it is maximal in this polynomial ring.

Thus, we have that

$$\Bbb F_9=\left\{\;0,\,1,\,2,\,w,\,2w,\,w+1,\,2w+1,\,w+2,\,2w+2\;\right\}$$

and with the addition and multiplication rule determined by addition and multiplication modulo $\;3\;$ and by $\;w^2=-1\;$ , for example:

$$(w+1)(2w+1)=2w^2+\overbrace{w+2w}^{=3w=0\cdot w=0}+1=2(-1)+0+1=-2+1=-1=2$$

and since $\;2^{-1}=2\pmod3\;$ , we get that

$$1=2\cdot2=(w+1)(2(2w+1))=(w+1)(w+2)\implies (w+1)^{-1}=w+2$$

in this field. Now you can play around with this.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • What would have happened or rather how this construction would have failed if I chose to build a field with 10 elements, not a power of prime. – Seetha Rama Raju Sanapala Mar 22 '16 at 09:36
  • @user3141822 Which construction? More precisely, what would your starting point be? – Tobias Kildetoft Mar 22 '16 at 09:38
  • @user3141822 Thanks to Tobias for the good comment. Now, how would you construct such a quotient ring? Over what prime (finite) ring: $;\Bbb F_2;$ or $;\Bbb F_5;$ ? Or else: suppose you reach some construction without referring to polynomial rings and all that: then what would the characteristic of a field with ten elements be? I think that pretty quickly you will run into this or that problem. – DonAntonio Mar 22 '16 at 09:58
0

$GF(9)$ is by definition the splitting field of $X^9-X$. So the elements are the roots of $X^9-X$ (except the root $0$ it's not easy at all to find them. We usually need a computer). In general, $GF(p^m)$ is the splitting field of $X^{p^m}-X$. Now, it can be interesting for you to prove that $$\{x\mid x^{p^m}-x=0\}$$ is really a field.

Surb
  • 55,662
0

To give $\def\F{\mathbf F}\F_9$ (or $\F_{p^m}$ in general), we start with $\F_3$ ($\F_p$) an an irreducible polynomial of degree $2$ over $\F_3$. As $p(X) = X^2 + 1$ has no roots in $\F_3$ ($p(0) = 1$, $p(1) = 2$, $p(2) = 2$), $p$ is irreducible. Now we define $\F_9 := \F_3[X]/(p)$. That is the elements of $\F_9$ are (in this representation), the classes $\pmod{(p)}$ represented by $$ 0, 1, 2, X, X+1, X+2, 2X, 2X+1, 2X+2 $$
Addition and multiplication is Addition and multiplication of polynomials $\pmod p$. For example, $$ (X+2) \cdot (X+1) = X^2 + 3X + 2 = X^2 + 2 = (X^2 + 1) + 1 = 1 \pmod {X^2 +1} $$ That $\F_9$ is a field follows from the irreducibility of $p$.

martini
  • 84,101