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.

  • 4
    $\begingroup$ Addition will be preserved for some choice of primitive element, but not all (because different primitive elements may have different characteristic polynomials). How about just starting with the multiplicative identity and going from there? $\endgroup$ – Qiaochu Yuan Jul 28 '11 at 15:36
  • $\begingroup$ Do you also know the addition tables? $\endgroup$ – Zhen Lin Jul 28 '11 at 15:37
  • 3
    $\begingroup$ If your fields have size $q = p^n$, for $p$ a prime, is it practical for you to factorize $x^q - x$ into irreducibles in ${\rm GF}(p)[x]$. Find an irreducible factor of degree $n$, and then identify a root of it in each of your (pairs of) tables. $\endgroup$ – Geoff Robinson Jul 28 '11 at 15:46
  • 1
    $\begingroup$ Extending @Geoff's idea, since I presume your tables are computed by some form of polynomial multiplication modulo some polynomial, you must already know what the minimal polynomials of the generator on both sides are. Then it suffices to find a root of one minimal polynomial in the other field to obtain the isomorphism. If your field isn't too large, this is a little less impractical than trying to factor $x^q - x$. $\endgroup$ – Zhen Lin Jul 28 '11 at 16:11
  • 2
    $\begingroup$ @Michael: If $p$ is a prime, and $n$ is a positive integer, there is, as you know, a unique field of order $p^n$ up to isomorphism. But given two fields of order $p^n$, there are exactly $n$-isomorphisms from one to the other. This is because a field of order $p^n$ has a cyclic automorphism group of order $n$, generate by $\alpha \to \alpha^p$. $\endgroup$ – Geoff Robinson Jul 28 '11 at 21:56

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.


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.