Title: Computing isomorphisms and embeddings of finite fields,
Abstract: Let $\mathbb{F}_q$ be a finite field. Given two irreducible polynomials $f,g$
over $\mathbb{F}_q$, with $\mathrm{deg} f$ dividing $\mathrm{deg} g$, the
finite field embedding problem asks to compute an explicit description of a
field embedding of $\mathbb{F}_q[X]/f(X)$ into $\mathbb{F}_q[Y]/g(Y)$. When
$\mathrm{deg} f = \mathrm{deg} g$, this is also known as the isomorphism
problem.
This problem, a special instance of polynomial factorization, plays a central
role in computer algebra software. We review previous algorithms, due to
Lenstra, Allombert, Rains, and Narayanan, and propose improvements and
generalizations. Our detailed complexity analysis shows that our newly proposed
variants are at least as efficient as previously known algorithms, and in many
cases significantly better.
We also implement most of the presented algorithms, compare them with the
state of the art computer algebra software, and make the code available as open
source. Our experiments show that our new variants consistently outperform
available software.