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

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.