$\begingroup$
$\endgroup$
Suppose $K$ is a number field and $f \in K[x]$ is irreducible. What is the computational complexity of computing f.splitting_field()? I'm also interested in the case we also compute an embedding, f.splitting_field(map=True) in SageMath.
If $deg(f)=n$, naively constructing a splitting field seems like it would take at most $n$ big steps, and substeps we must factor $p(X)$, and also find a root. I think the LLL algorithm implies factoring over $\mathbb{Q}$ is polynomial time, but I'm not sure about number fields.
It seems like it should be polynomial time overall, but in practice it crashes frequently.