Suppose you have a finite field extension $\mathbb Q \subset K$ and an irreducible polynomial $P \in K[X]$.
Let $L$ be the Galois closure of $K$, $G$ be the Galois group of $\mathbb Q \subset L$, and $H$ be the subgroup of $G$ fixing $K$. Then $G$ acts on $L[X]$ by $\sigma(\sum a_i X^i) = \sum \sigma(a_i)X^i$, and $H$ is still the subgroup of $G$ fixing $K[X]$.
Then define $\tilde{P} = \prod_{\sigma \in G/H} \sigma(P)$. For any $\sigma$ in $G$, $\sigma(\tilde{P}) = \tilde P$, thus $\tilde P \in \mathbb Q[X]$, and I think it should be irreducible over $\mathbb Q$ if $K$ is the extension generated by the coefficients of $P$.
And so far, the computation is polynomial in the degree of the extension $\mathbb Q \subset L$ (which may be exponential in the degree of $K$) and in the degree of $P$.
If you don't know exactly what $L$ and $G$ are but you know the set of conjugates $C_i$ of each coefficient $a_i$ of $P$, define
$$\tilde P = \prod_{(b_0, \ldots, b_n) \in C_0 \times \ldots \times C_n} (b_0 + b_1 X + \ldots b_n X^n)$$
This will produce a polynomial in $\mathbb Q[X]$, but can be extremely larger than the minimal polynomial.
Here you pick one conjugate for each coefficient, and you do the product for all possible simultaneous choices of those conjugates. If you have one coefficient with 2 conjugates and another one with 3, and all the other coefficients are rationals, then you have 6 polynomials to multiply.
Finally, if you don't know the conjugates of the coefficients but you know some annihilating polynomial for each coefficient, let $C_i$ be a set of formal roots of those polynomials, and formally expand that product. You will get an expression involving the formal roots symmetrically so you can write it using the elementary symmetric polynomials of those roots, and then use the Viete relations and replace those with the corresponding coefficients of your annihilating polynomials.
However, these two methods can be exponential in the degree of $P$, so you should avoid them if possible.
In the worst case scenario, the Galois group of $\mathbb Q \subset K$ will be $S_n$, meaning that we have to do calculations in a very big field extension.
suppose $K$ is of degree $n$ and $P$ is of degree $d$. We can estimate of the generic formula you need to use to transform $P$ into a polynomial with rational coefficients.
Pick $L = \mathbb Q(Y_1, \ldots, Y_n)$, let $Z_1, \ldots, Z_n$ be the elementary symmetric polynomials in $Y_i$, pick $K_0 = L^{S_n} = \mathbb Q(Z_1, \ldots, Z_n)$, and $K = K_0(Y_1)$ So the extension $K_0 \subset K$ is the "generic" extension of degree $n$ over $\mathbb Q$.
Then say $P = \sum a_i X^i$, where $a_i \in K = K_0[Y_1]$ and are of degree $ < n$.
So you can write $P = \sum b_{i,j} X^i Y_1^j$ where $b_{i,j} \in K_0$, and $(i,j) \in \{0 \ldots d \} \times \{0 \ldots n \}$. Add indeterminates $B_{i,j}$, so that now $P$ is an element of $K[B_{i,j},X]$. We can compute the product $\prod_{k=1}^n P(Y_k,B_{i,j},X)$ in $L[B_{i,j},X]$, then since it is symmetric, write it as an element of $K_0[B_{i,j},X]$.
In fact since the coefficients of $P$ are polynomials in $Y_1$ with integer coefficients, this will be a polynomial in $\mathbb Z[Z_i, B_{i,j},X]$ of degree $dn$ in $X$, homogeneous of degree $n$ in the $B_{i,j}$.
For any choice of $n$ indeterminates among the $B_{i,j}$, $B_{i(1),j(1)} \ldots B_{i(n),j(n)}$ will appear accompanied with $X^{i(1)+\ldots i(n)}$ and a polynomial in $Z_k$ of degree $j(1)+\ldots j(n) \le n^2$ in $Y_k$. So we obtain less than about $(n+d)!/n!d! * n^{2n}/n!$ terms in the final polynomial. Though there may be a better bound on the complexity of polynomials in $Z_k$ that are of a given degree less than $n^2$ than $n^{2n}/n!$ (in particular, not all of them should be able to appear).
Well the good thing it that this is polynomial in $d$ when $n$ is fixed, and is probably exponential in $n$ when $d$ is fixed. And when both of them vary, it's exponential in $d$ and $n$.
Here's one way --- I don't know how efficient it is.
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$.
Best Answer
As in https://mathoverflow.net/a/26859/10423, if your number $x$ ($p(x)=0$) is a sum of two algebraic numbers $y, z$, and $[\mathbb{Q}(y): \mathbb{Q}]$ and $[\mathbb{Q}(z): \mathbb{Q}]$ are relatively prime, we would have $$ \mathbb{Q}(x) = \mathbb{Q}(y, z). $$ To use this, we might look for subfields $\mathbb{Q}(y) \subset \mathbb{Q}(x) $ generated by particularly simple elements $y$ ($q(y)=0$). Then $x$ would satisfy a polynomial equation $r(x)=0$ of degree $\deg(x)/deg(y)$ whose coefficients are themselves polynomials in $y$.
This can be done in sage. Define the number field generated by your number in the comment:
then loop through all subfields $\mathbb{Q}(y)$ generated by sage's
K.optimized_subfields:This code considers, in turn, each subfield generated by $y$, and prints out the polynomials $q(y)\in\mathbb{Q}[y]$ and polynomial $r(x)\in\mathbb{Q}(y)[x]$, checking whether $r(x)$ can be written as a polynomial in $x-y=z$ with integer coefficients.
There are 12 subfields, snipping part of the output, some of the $y$'s are quite simple:
$$ x = -\sqrt{2} + \mathrm{Root}_w(w^3-6w^2+12w-10) $$
$$ x = -2-y^2-y^3, \qquad y = -2^{1/6} $$
One might also check for all simple linear expressions $x = z + \lambda y$ by expanding $r(z+\lambda y)$ and checking whether all coefficients of $x^{\geq0}y^{>0}$ can be set to $0$ by a particular choice of $\lambda\in\mathbb{Z}$.
In my testing, I used the root near $-72.5006$ of
which is
$$ 7 \mathrm{Root}_{x\approx-1.214}(8 + 3 x^3 + x^5) + 8 \mathrm{Root}_{x\approx-8.000}(2 + 8 x^4 + x^5). $$
So it works for $\deg(x)=25$, but in general it probably takes exponential time or worse, not polynomial. On the plus (?) side it generalizes the problem from looking for sums (not products, though) to looking for polynomial relations with algebraic coefficients.