Finding all finite field embeddings

Question

Does there exist an efficient (i.e. sub-exponential) algorithm for finding all possible embeddings of one finite field into an isomorphic field? I'm particularly interested in ways to embed $GF((2^2)^2)$ into $GF(2^4)$ and $GF(((2^2)^2)^2)$ into $GF(2^8)$. Finding a single embedding can be easily done using tools like Magma, but as far as I know this embedding is selected at random the approach discussed here (http://www.sciencedirect.com/science/article/pii/S0747717197901383). Beyond from trying the embedding many, many times and hoping that all possibilities are covered, I was not able to find a enumerate all of these embeddings. Does anyone know how? Better yet, if there is support to do this in Magma, can someone provide an example?

Answer 1

As the multiplicative group of a finite field $\mathbb F_{p^n}$ is cyclic, just pick a generator $g$ of $\mathbb F_{p^n}^\times$ and try the maps $g\mapsto g^k$ with $1\le k< p^n$ and $(k,p^n-1)=1$. Especially, the case $k=p$ is called Frobenius automorphism.

Answer 2

Suppose $k$ and $k'$ are finite fields of size $q$ and $q'$ respectively and characteristic $p$, with $q=p^f$. If you can efficiently find one embedding $\iota: k \rightarrow k'$, you can find all others by composing $\iota$ with $\sigma^m$ for $0<m<f$, where $\sigma: x \mapsto x^p$ is the generator of $\text{Aut}(k)$. (note that $\sigma$ can be evaluated efficiently by square-and-multiply).