Finding isomorphisms between finite fields.

Question

I'm having trouble understanding how to find isomorphisms between finite fields. In my lecture notes it uses the following theorem:

A function $f$ is an isomorphism from $GF(z^n)$ represented modulo $p(X)$ to $GF(z^n)$ represented modulo $q(Y)$ if and only if $f$ commutes with addition and multiplication, $f (1) = 1$ and for $b = f(X)$, $(X - b)$ divides $p(X)$ as polynomials modulo $q(Y)$.

How can you use this to find isomorphisms? Say for example, between $GF(2^8)$ with $p(X) = X^8+X^4+X^3+X+1$ and $q(Y) = Y^8 +Y^4 + Y^3 + Y^2+ 1 $...?

Answer 1

You may observe that $X+1$ has order $255$ (multiplicatively) in the first representation, i.e., the multiplicative group of $\Bbb F_2[X]/(p(X))$ is generated by $X+1+(p(X))$. On the other hand, in the second representation already $Y$ itself has order $255$. This suggests we map $X+1+(p(X))\mapsto Y+(q(Y))$. As necessarily $a\mapsto 1$, this means $X+(p(X))\mapsto Y+1+(q(X))$. And verily, a quick calculation reveals that $$\begin{align}p(X+1)&=(X+1)^8+(X+1)^4+(X+1)^3+(X+1)+1\\ &=(X^8+1)+(X^4+1)+(X^3+X^2+X+1)+(X+1)+1\\ &=X^8+X^4+X^3+X^2+1\\ &=q(X).\end{align}$$ Without the irder calculation I mentioned in my first paragraph, you might simply have tried a few simple maps $X\mapsto r(X)$, and in fact $r(X)=X+1$ should have been among the first to try ...

Answer 2

I have worried about this question in more general contexts for quite some time. Hagen’s solution of your particular problem was quick, and I think, lucky. There are thirty irreducible polynomials of degree $8$ over $\Bbb F_2$, and if it were some other pair of these than the ones given to you, you might have had a lot of trouble just floundering about, as I think Hagen’s closing advice was.

Here’s a general strategy that I think you might be able to use in more complicated cases. You have in hand the explicit description of two fields, say $K$ and $L$, which you know are isomorphic because they both have $256$ elements. You were told the $f$ and $g$ with $K=\Bbb F_2[X]/(f)$ and $L=\Bbb F_2[X]/(g)$. The multiplicative group in each field is of order $255=3\cdot5\cdot17$, so that there are elements of order $17$ in each group. Say that $\xi$ is such an element in $K$. Then $K=\Bbb F_2(\xi)$, because no smaller field contains elements of order $17$ ($n=8$ is the smallest number such that $17|(2^n-1)\>$.)

Now, the minimal polynomial of $\xi$ is \begin{align} F(X)&=(X-\xi)(X-\xi^2)(X-\xi^4)(X-\xi^8)(X-\xi^{16})(X-\xi^{32})(X-\xi^{64})(X-\xi^{128})\\ &=(X-\xi)(X-\xi^2)(X-\xi^4)(X-\xi^8)(X-\xi^{16})(X-\xi^{15})(X-\xi^{13})(X-\xi^9)\,, \end{align} coefficients in $\Bbb F_2$, and you can use it for re-expressing $K$ as $\Bbb F_2[X]/(F)$. It’s an irreducible octic whose roots are eight of the $16$ primitive $17$-th roots of unity in your field.

Now do the same for an element $\zeta\in L$ that you have found that’s of period $17$. You’ll get an $\Bbb F_2$-polynomial $G$ to re-express $L$ as $\Bbb F_2[X]/(G)$. But there are only two octic polynomials whose roots are primitive $17$-th roots of unity. If you’re in luck, then $F=G$, and you immediately get an isomorphism between $K$ and $L$. But if $G$ is the other octic, then $\overline G=(X-\zeta^3)(X-\zeta^5)(X-\zeta^6)(X-\zeta^7)(X-\zeta^{10})(X-\zeta^{11})(X-\zeta^{12})(X-\zeta^{14})$ is equally well a polynomial such that $L=\Bbb F_2[X]/(\overline G)$, and $\overline G=F$, giving you your isomorphism between $K$ and $L$.