# minimal polynomial of power of algebraic number

Consider any algebraic number $\alpha$ which is given by its minimal polynomial $f$. How can I compute the minimal polynomial of $\alpha^m$ for some natural number $m$? How efficient the algorithm is?

I assume that this problem is well-studied, but can anyone give me a reference, or some short description of the algorithm?

Thanks a lot!

-
I think the minimal polynomial of $\alpha$ and the minimal polynomial of $\alpha^m$ are not strongly related. (Except of course in some special cases.) – rschwieb Oct 19 '12 at 12:09
thanks. Somehow this question can be formulated as given $\alpha$, how to compute (symbolically) $\alpha^m$. I guess there must be some algorithm to do so. – user29271 Oct 19 '12 at 12:23

You know the polynomial for $\alpha$. Say it has degree $d$. That means you can express any power of $\alpha$ as a rational linear combination of $1,\alpha,\dots,\alpha^{d-1}$. In particular, you can express any power of $\alpha^m$ as such a linear combination. Then you can test, for various $r$, whether $1,\alpha^m,\alpha^{2m},\dots,\alpha^{rm}$ is a linearly independent set over the rationals. As soon as you get a set that isn't, you have your minimal polynomial for $\alpha^m$.
EDIT: For example, suppose $\alpha$ is a zero of $x^3-x-1$, and find a polynomial for $\beta=\alpha^2$. Well, $\alpha^3=\alpha+1$; $\alpha^4=\alpha^2+\alpha$; $\alpha^5=\alpha^3+\alpha^2=\alpha^2+\alpha+1$; $\alpha^6=\alpha^3+\alpha^2+\alpha=\alpha^2+2\alpha+1$. We find that $1,\beta,\beta^2,\beta^3$ are linearly dependent: $2\beta^2-\beta^3=\beta-1$. So our polynomial is $x^3-2x^2+x-1$.