Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$.

I'm looking for a pointer towards the fastest (in term of arithmetic complexity, say) currently known method to factor a given polynomial $P\in \mathbb{K}[z]$ of degree $d$. More precisely, I'd like to know a reasonable bound on said complexity in terms of $P$ (its degree $d$ and the maximum degree $n$ of the minimal polynomials defining its coefficients).

As an aside I'm also interested in theoretical results regarding complexity of approximate root-finding algorithms in the case of BSS computation model, in terms of the degree of $P\in \mathbb{C}[z]$ and the magnitude of the desired approximation.

thatquestion. $\endgroup$ – Emil Jeřábek 3.0 Mar 29 '16 at 13:03