Find the isomorphism between two table representations of the same finite field

Question

I am given two multiplication and addition tables for a finite field (i.e. the tables are for different naming of the elements of the field) and I want to find the isomorphism between the two representations. One idea is to map a primitive element of the first field to a primitive element of the second field and define the rest of the mapping according to their powers, but I am not sure addition is preserved in this method.

Answer 1

The following is a collection of the ideas posted in the comments together with some of my own thinking. This is too long to fit into a comment, and I think this works with reasonable complexity even assuming that you have no other information available than the addition and multiplication tables for the two fields. I'm all ears to suggestions for improvements and better solutions. I think that it is highly likely that my approach can be improved.

1. First we know the characteristic $p$ and the degree of extension $n$ over the prime field simply from the size of the tables. So at this point we know that both fields are isomorphic to $GF(p^n)$, and have cyclic Galois groups generated by the Frobenius map $F:x\mapsto x^p$. We can also easily identify the elements of the prime field, as spotting $0$ and $1$ is easy, and generating $2=1+1,3=2+1,\ldots,p-1$ is also straightforward.
2. Partition both fields into disjoint unions of orbit under the Galois group. The orbit of an element $x$ consists of the elements of the form $F^i(x)$ for $i=0,1,\ldots$. Note that for some integer $d$ we have $F^d(x)=x$, and furthermore it always happens that the smalles such $d$ is a factor of $n$. Here the exponent of $F$ denotes iteration, so $F^2(x)=F(F(x))$, $F^3(x)=F(F^2(x))$ et cetera. Also note that in the case $p=2$ the Frobenius map is just squaring, and its value can be immediately read from the multiplication table. If you want to spend less time with this step, I will disclose that it suffices to find one orbit of a maximal size $n$ from one of the fields.
3. Next I will locate a vector space basis (over the prime field) for one of the fields. With the partition of step 2 at hand (even to the extent described in the last sentence of step 2) this is easy. Let $\alpha$ be an element in an orbit of maximal size $n$. Then $\alpha$ generates the field as an extension over the prime field, and we can use $\mathcal{B}=\{1,\alpha,\alpha^2,\ldots,\alpha^{n-1}\}$. Identifying all these elements using the multiplication table is straightforward.
4. Next I describe a method for finding the coordinates of a given element with respect to the basis $\mathcal{B}$. The method depends on the fact that the bilinear form $(x,y)=Tr(xy)$ is non-degenerate. Here $$ Tr(x)=x+F(x)+F^2(x)+\cdots+F^{n-1}(x)=\sum_{i=0}^{n-1}F^i(x), $$ and (this is important) its values belong to the prime field, and can thus be identified. The non-degeneracy of this bilinear form means that $0$ is the only element $y$ with the property: $(x,y)=0$ for all $x$. So given an element $\beta$ we want to find elements $x_i,i=0,\ldots,n-1$ of the prime field such that $\beta=\sum_i x_i\alpha^i$. The coordinates are the (unique) solution to the linear system of equations given by $$ (\beta,\alpha^j)=\sum_i x_i(\alpha^i,\alpha^j), $$ where $j=0,1,\ldots,n-1$. Such a system can be solved by e.g. Gaussian elimination. IOW it has complexity that is polynomial in $n$ and thus gives a marked improvement to brute force search of all combinations - at least if $n$ is a bit larger. If $p^n$ is small, then brute force may be better, because you avoid the computation of $n(n+1)/2$ traces - your call. [Edit: non-degeneracy of the trace form manisfests itself here in the helpful way that the matrix $((\alpha^i,\alpha^j))_{i,j=1}^n$ is non-singular.]
5. Next we determine the minimal polynomial $m(x)$ of $\alpha$. This is easy, because all we need to do is to apply the method of step 4 to $\beta=\alpha^n$.
6. The remaining task is to locate a zero of the polynomial $m(x)$ from the other field. We know in advance that all the zeros form a Frobenius orbit of size $n$, so we only need to check such elements, one representative from each orbit untill we get lucky. Constructing the isomorphism is then easy.

I really hope that there is something better than step 6. That has exponential complexity as a function of $n$ as does step 2. May be doing steps 3-5 to both fields helps? We only need one full size orbit to do steps 3-5, and a random element is more likely than not to have a full size orbit, so we may not need the full partition of step 2.

This is unsatisfactory, so hopefully we can continue this as a group effort. The main contribution of my answer is the method of finding a monomial basis and the related minimal polynomial using the trace-form.