Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}\_p$, both of degree $n$. We know that factor-rings $\mathbb{F}\_p[x]/(f)$ and $\mathbb{F}\_p[x]/(g)$ are isomorphic (both of them is isomorphic to $\mathbb{F}\_{p^n}$). 


My question is: Is it possible to make this isomorphism *efficient*? I.e. can we find a matrix that makes an isomorphism between $\mathbb{F}\_p[x]/(f)$ and $\mathbb{F}\_p[x]/(g)$ for poly(n) operations in $\mathbb{F}\_p$?



An efficient isomorphism between finite fields
Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (Mathematics of Computation, v. 56 (1991), 329-347). Another algorithm appears in the paper by B. Allombert, "Explicit computation of isomorphisms between finite fields" (Finite Fields and their Applications, v. 8 (2002), 332-342). However, the latter paper does not describe the running time of its algorithm, beyond saying that it is fast. An excellent survey of algorithms in number theory is H. W. Lenstra, Jr., "Algorithms in algebraic number theory" (Bulletin of the American Mathematical Society, v. 26 (1992), 211-244). Although it was written 25 years ago, still this is well worth reading.


