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.



Finding an embedding efficiently in field extension of finite field
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.


