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.

  • $\begingroup$ The question only makes sense for the usual Boolean computational model, and for a particular representation of a particular field by binary strings. You can't compute exact roots by an arithmetic circuit or by a BSS machine, as any value computed in such models is the value of a rational function of the inputs. $\endgroup$ – Emil Jeřábek 3.0 Mar 29 '16 at 10:30
  • $\begingroup$ That's true, and that's the aim of my main question with coefficients in $\overline{\mathbb{Q}}$. The side question was to know the complexity in BSS model being given an error bound on the result (like with Newton method, but I guess better methods exist out there, the difficulty being in finding initial conditions in every eventually-attractive bassin. I know people from complex dynamics studied that and proposed algorithms). I'll edit the question to reflect this clarification. $\endgroup$ – Loïc Teyssier Mar 29 '16 at 12:24
  • $\begingroup$ But the main question is still totally unclear. You write “arithmetic complexity”, but that does not make sense, as arithmetic circuits can’t compute roots exactly. And even if I ignore vague words like “typically” and just assume you mean to ask about $\overline{\mathbb Q}$, you did not specify the representation of the field. The time complexity of computing with algebraic numbers in the isolating interval representation and in the sign-sequence representation may be quite different, for instance. Either way, the task of “exact root finding” over the algebraic numbers will mostly ... $\endgroup$ – Emil Jeřábek 3.0 Mar 29 '16 at 13:02
  • $\begingroup$ ... consist of factoring of polynomials in $\mathbb Q[x]$, so it might be clearer if you asked that question. $\endgroup$ – Emil Jeřábek 3.0 Mar 29 '16 at 13:03
  • 1
    $\begingroup$ Hopefully an expert will weigh in and answer your question, but the wikipedia page (en.wikipedia.org/wiki/Factorization_of_polynomials) on polynomial factoring seems quite relevant. In particular, your problem easily reduces to factoring over $\mathbb{Q}$ by Trager's method, and then factoring rational polynomials takes only polynomial time. You might ask an expert in Trager's method about the complexity of that algorithm. $\endgroup$ – Pace Nielsen Mar 29 '16 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.