Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.