The following solves the problem of finding the minimal polynomial of $\alpha^i$ given the minimal polynomial of $\alpha$. If you know the exponent $e$ in $\beta=\alpha^e$, then you can apply this to your question. This has much higher complexity than taking the reciprocal as I indicated in a comment under the OP.
Assume that we know the minimal polynomial $m(x)$ os a primitive $n$th root $\alpha$, and that we want to calculate the minimal polynomial of another primitive root $\beta=\alpha^i$, $\gcd(i,n)=1$. First we find the modular inverse $j$ of $i$, so this is an integer with the property $ji\equiv1\pmod n.$ We then know that $\beta^j=\alpha$. Thus we know that $\beta$ is a zero of the polynomial $m(x^j)$.
As $\beta$ is also a zero of $x^n-1$ we know that $\beta$ is a zero of
$$
m_j(x):=\gcd(x^n-1,m(x^j)).
$$
I claim that $m_j(x)$ is the minimal polynomial of $\beta$. Let $\gamma$ be any zero of $m_j(x)$. As $m_j(x)\mid x^n-1$, we know that $\gamma$ has to be an $n$th root of unity, so $\gamma=\alpha^t$ for some integer $t$. As $\gamma^j$ is a zero of $m(x)$, we know that $\gamma^j$ is a conjugate of $\alpha$, i.e. $\gamma^j=\alpha^{p^k}$ for some non-negative integer $k$. But this means that
$$
\gamma=\gamma^{ij}=\alpha^{ip^k}=\beta^{p^k}
$$
is a conjugate of $\beta$. Thus all the zeros of $m_j(x)$ are conjugates of $\beta$ proving the claim.
As an example let's take the irreducible factor $m(x)=x^2+5x+1$ of $x^{12}-1$ in the ring $\mathbb{Z}_{11}[x]$ given by Gils in a comment. We could check that the roots of $m(x)$ are, indeed, primitive twelfth roots of unity, but I'll skip that. We observe right away that $m(x)$ is palindromic, i.e. equal to its own reciprocal polynomial. This was to expected. For if $\alpha$ is a zero of $m(x)$, then the other zero is the Frobenius conjugate $\alpha^{11}=\alpha^{11-12}=\alpha^{-1}$. But we can use $j=5$ here as $\gcd(5,12)=1$. The above piece of theory tells us to calculate (Mathematica did this for me)
$$
m_5(x):=\gcd(m(x^5),x^{12}-1)=\gcd(x^{10}+5x^5+1,x^{12}-1)=x^2+6x+1=x^2-5x+1.
$$
This is the other factor given by Gils. Its roots are $\alpha^5$ and $\alpha^{-5}=\alpha^7$. As an auxiliary check we observe that this time we knew that $\alpha^6=-1$ as that is the sole primitive second root of unity. Therefore $\alpha^7=\alpha\alpha^6=-\alpha$. Indeed, we immediately see that
$m_5(x)=m(-x)$. This gives us another proof for the fact that $\alpha^7=-\alpha$ is a zero of $m_5(x)$
This method may not always be very low complexity, because the polynomial $m(x^j)$ may have a rather high degree, and calculating the gcd thus takes a while (with the pen & paper method). Some help can be gotten by replacing $x^n-1$ with the characteristic zero $n$th cyclotomic polynomial $\phi_n(x)$ of degree $\phi(n)<n$.
