This should be a fairly trivial question, to which I have nevertheless found no satisfactory answer.
I am interested in effective algorithmic computation of minimal polynomials of some particularly simple algebraic numbers, especially the complex $n$-th roots of rational numbers: $$\alpha = \sqrt[n]{q}e^{i2k\pi/n}.$$ Each such $\alpha$ is a root of the polynomial $x^n - q$, but the trouble is that this polynomial might not be irreducible over $\mathbb{Q}$. I know that the irreducible factors can be found in polynomial time, e.g., using the LLL algorithm. But how to determine the correct factor? This can usually be done easily by hand, but what about algorithmic computation? The only way of evaluating a polynomial at $\alpha$ that I am aware of already assumes that the minimal polynomial of $\alpha$ is known. Or should I use a completely different approach?
Moreover, since $q$ can be assumed to be an integer, an algorithm for computing minimal polynomials of algebraic integers would be sufficient. This MathOverflow answer suggest that computing minimal polynomials of algebraic integers is easy, but I was unable to find out why. Any reference would be helpful here.
Thank you in advance.
