1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 3, 2011 at 20:48

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .