Finding an embedding efficiently in field extension of finite field

We know that $GF(p^c)$ is a subfield of $GF(p^{cn})$. Also we know that elements in $GF(p^c)$ can be represent by degree $c$ polynomials with coefficients in $\mathbb Z_p$, where multiplication is done by usual polynomial multiplication modulo a degree $c$ irreducible polynomial $p$.

The question is, given the representation of $GF(p^c)$ and $GF(p^{cn})$ (by giving the two irreducible polynomials), can we find what an element in $GF(p^c)$ should be in the representation of $GF(p^{cn})$? Can it be found in polylog($p^c$) time?

It would be really helpful if you could also provide some references.

-
Remember that you will only find the element 'up to conjugacy'. A trick researchers in finite fields often use is to use a primitive polynomial to generate the bigger field. Then you can pick the relative norm of that generator as a generator for the smaller field. That makes it easy to, e.g. align multiplicative characters. This doesn't answer your question because then the lower degree primitive polynomial will be determined (shouldn't be too hard to compute either). May be that route is not open to you? – Jyrki Lahtonen Oct 3 '11 at 20:48

1 Answer

H. Lenstra Finding isomorphisms between finite fields, Math. Comp. 56 (1991), 329–347.

BTW $O(polylog\ {p^{cn}})$ because the answer typically won't be sparse.

-