8
$\begingroup$

An algebraic number is defined as a root of a polynomial with rational coefficients.

It is known that every algebraic number $\alpha$ has a unique minimal polynomial, the monic polynomial with rational coefficients of smallest degree of which $\alpha$ is a root.

It is also known that the algebraic numbers are algebraically closed, meaning that any polynomial with algebraic numbers as coefficients has algebraic roots.

My question is:

Given the root of a degree $d$ uni-variate polynomial with $n$ terms with algebraic coefficients, is there an efficient (i.e. polynomial time in $d$ and $n$) algorithm to generate its minimal polynomial?

I have searched the literature, but found very little work on algebraic number theory concerned with computational complexity. The closest result I found is:

Theorem 1.4.7 in Lovasz's book:

http://books.google.co.uk/books?id=NWa5agInx0gC&lpg=PA39&ots=ufoR8afRSQ&dq=finding%20the%20minimal%20polynomial%20for%20a%20root%20of%20a%20polynomial%20%20lovasz&pg=PA38#v=onepage&q&f=false

but I don't think this (quite) answers my question.

  • 0
    If there is no algorithm for computing the minimal polynomial, an efficient algorithm for finding any polynomial with *rational coefficients* for which this number is a root, will suffice.2012-06-22
  • 0
    One generally finds the minimal polynomial of an algebraic number, not of a polynomial. Could you please clarify your question?2012-06-22
  • 0
    I have done so. Thanks for your careful reading!2012-06-22

1 Answers 1