Expressing a root of a polynomial as a rational function of another root

If $f$ has abelian Galois group and you can find an explicit embedding of its splitting field into $\mathbb{Q}(\zeta_n)$, you get a quotient map $(\mathbb{Z}/n\mathbb{Z})^{\ast} \to \text{Gal}(f)$ which makes the action of the Galois group quite explicit. Applying elements of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ to a root $a$ of $f$ in $\mathbb{Q}(\zeta_n)$ gives you some explicit expressions in $\mathbb{Q}(\zeta_n)$ which you can then try to express as polynomials in $a$. I don't know how easy this will be to do, though, but in certain cases it is fairly explicit: for example if $f$ is the minimal polynomial of $2 \cos \frac{2 \pi}{n}$ you get Chebyshev polynomials.

I haven't found a stellar way to do this by hand, but it is now easy to do with Pari/GP. The basic idea is you just factor f over Q[x]/(f).

Often this is easy to do: find some prime p in Q such that {x,x^p,x^(p^2),…} has exactly deg(f) distinct residues mod (f,p). Choose p larger than the twice the largest coefficient of the ones in the (unknown) answer. Replace a mod p with the integer of smallest absolute value congruent to a mod p for each of the coefficients of x^(p^i) mod (f,p). Check that the formula works. I had to take p=31 in the particularly 6th degree case, so this is not exactly great for by hand exams.

There are more refined versions of factoring using Hensel lifting or combining several primes both of which allow smaller primes to be used (and for it to work in general). The details of one (or two) algorithms are in section 3.6.2 of Henri Cohen's textbook for a Course in Computational Algebraic Number Theory, and some others are also in the source code to Pari/GP (with references).