Polynomials for which roots can be expressed as polynomials in a single root Classical Galois theory gives necessary and sufficient conditions for the roots of a polynomial in $k[x]$ to be expressible in terms of nested radicals of the coefficients.
Suppose instead that a single root $\alpha$ of $p(x)\in \mathbb{Q}[x]$ is known. Are there known necessary and sufficient conditions on $p(x)$ such that all remaining roots can be expressed as polynomial (or rational) functions of $\alpha$ and the coefficients of $p(x)$?
For example, the cyclotomic polynomials have this property, since every primitive $n^{\textrm{th}}$ root of unity can be written as a power of some fixed root.
 A: Let $\alpha=\alpha_1$, $\alpha_2$, ..., $\alpha_n$ be the roots of $p(x)$. You want $\mathbb{Q}(\alpha_1,\alpha_2, \ldots, \alpha_n) = \mathbb{Q}(\alpha)$. If the Galois group is $G \subseteq S_n$, then $\mathbb{Q}(\alpha_1)$ corresponds to the stabilizer of $1$ in $G$, and $\mathbb{Q}(\alpha_1,\alpha_2, \ldots, \alpha_n)$ corresponds to the trivial subgroup. So the condition is that the stabilizer of $1$ in $G$ is trivial.
In other words, the action of $G$ on the orbit of $\alpha_1$ should be regular.
All of this was basically said in comments above, but their seemed to be some confusion about the case where $p(x)$ has multiple factors, so here is an answer which doesn't assume that $p$ is irreducible.

As per discussion in comments, let $L/K$ be a Galois extension with Galois group $G$; put $N = |G|$. Let $\alpha \in L$ be an element with trivial stabilizer. Let $\beta$ be an other element of $L$. We want to write $\beta$ as a polynomial in $K(\alpha)$. Set $\gamma_j = \text{Tr}_{L/K}(\alpha^j \beta)$. Then the $\gamma_j$ are in $K$. If $K = \mathbb{Q}$ and $\alpha$ and $\beta$ are algebraic integers, then the $\gamma_j$ are integers.
For any nonnegative integer $j$, we have
$$\text{Tr}_{L/K}(\alpha^j \beta) = \sum_{\sigma \in G} \sigma(\alpha)^j \sigma(\beta).$$
If, for some magic reason, we explicitly have floating point values for the $\sigma(\alpha)$ and $\sigma(\beta)$, and know the $G$-action on these values, we can use this formulato numerically compute the $\gamma_j$; if the $\gamma_j$ are then integers, we can round our computations to the nearest integer and get the result. In practice, I'm not sure how you'd get the $\gamma_j$, but I'll pretend you know them.
Let $A$ be the $N \times N$ matrix with entries $\sigma(\alpha)^j$ for $0 \leq j \leq N-1$. Let $\vec{b}$ be the vector with entries $\sigma(\beta)$ and let $\vec{c}$ be the vector with entries $\gamma_j$. So the displayed equation above states that $A \vec{b} = \vec{c}$, and thus $\vec{b} = A^{-1} \vec{c}$. In particular, $\beta$ is the dot product of the first row of $A^{-1}$ with $\vec{c}$.
The entries of $\vec{c}$ are in $K$, so it remains to show that the entries of the first row of $A^{-1}$ are in $K(\alpha)$. Let the Galois orbit of $\alpha$ be $\{ \alpha_1, \alpha_2, \ldots, \alpha_N \}$ with $\alpha = \alpha_1$. Then $A$ is a Vandermonde matrix in the $\alpha_i$'s, so the first row of its inverse is
$$\pm \frac{e_i(\alpha_2, \alpha_3, \ldots, \alpha_n)}{\prod_{j=2}^N (\alpha_1 - \alpha_j)}. \qquad (\ast)$$
Let $p(x)$ be the polynomial $f(x)/(x-\alpha_1) = \prod_{j=2}^N (x-\alpha_j)$. Then the coefficients of $p$ are clearly in $K(\alpha_1)$. The numerator $e_i(\alpha_2, \alpha_3, \ldots, \alpha_n)$ of $(\ast)$ is (up to sign) the coefficient of $x^{n-i-1}$ in $p$, and the denominator is $p(\alpha_1) = f'(\alpha_1)$. So $(\ast)$ is in $K(\alpha_1)$ and we are done.
My memory is that I read that this was Galois's proof, but I couldn't find the source quickly.
A: From a computational point of view, one should not try to compute the Galois group. Assuming $p(x) \in \mathbb{Q}[x]$ is irreducible, and $\alpha$ is a root of $p(x)$, it is sufficient to factor $p(x)$ over the number field $\mathbb{Q}(\alpha) = \mathbb{Q}[x]/(p(x))$, and look whether all the irreducible factors have degree 1. In this way, you also get the expression of the roots in terms of $\alpha$. This is much less expensive than computing the Galois group, which is feasible only in relatively low degree.
