Suppose I have $p_1(x), p_2(x) \in GF(2)[x]$ and fields $F_1 = GF(2)[x]/p_1(x), F_2 = GF(2)[x]/p_2(x)$ where both are isomorphic to $GF(2^n)$.
I know that if $p_1(x) \neq p_2(x)$ then it is possible to show that $\operatorname{Tr}_{F_1}(x^k) = \operatorname{Tr}_{F_2}(\beta x^{jk})$ for some value of $j$ (an integer) and $\beta \in F_2$, where $j \nmid 2^n-1$. (Essentially the sequences $y_1[k] = \operatorname{Tr}_{F_1}(x^k)$ and $y_2[k] = \operatorname{Tr}_{F_2}(x^k)$ can be derived from each other by decimations and shifts.)
Is there any way to compute $j$, given $p_1$ and $p_2$, aside from trial and error? (The value of $\beta$ is easy to compute once you know $j$; I know how to do it in computer code by running an LFSR backwards given $n$ consecutive samples of $y_1[k]$ and $y_2[k]$ but not sure how to express it in math)
Note that $j$ is not unique and can be multiplied by any power of 2, yielding identical results with an appropriate change in $\beta$ — in particular $\operatorname{Tr}_{F_2}(\beta x^{jk}) = \operatorname{Tr}_{F_2}((\beta x^{jk})^d)$ with $d = 2^m$, if I did my math correctly, so a substitution of $j \mapsto dj$ and $\beta \mapsto \beta^d$ should leave the trace unchanged.
I finally asked this question on mathoverflow.net and got a very helpful answer.
The short answer is to follow essentially the following procedure:
Find any root $y_1 \in F_1$ of $p_2(y)$ in the polynomial ring $F_1[y]$ --- these are the polynomials $p(y)$ which have coefficients that are elements in $F_1$ and are themselves polynomials.
Take the discrete logarithm to determine $j$ such that $x^j = y_1$
I've written up a longer description in my blog post which includes the use of a factoring method that partitions $p(y)$ as $p(y) = \gcd(p(y),S(x^ky))\gcd(p(y),S(x^ky)-1)$ where $S(u) = u + u^2 + u^4 + u^8 + \ldots + u^{2^N-1}$, which is mentioned in Lidl + Niederreiter and also in http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/.