Representing an algebraic number in an algebraic number field

Let $\alpha$ be an algebraic number (with minimal polynomial $f$). Then $\mathbb{Q}(\alpha)$ is an algebraic number field, and elements of $\mathbb{Q}(\alpha)$ can be represented as polynomials of $\alpha$ with rational coefficients modulo $f$.
Let $\beta$ be an other algebraic number (with minimal polynomial $g$).
Then I would like to determine whether $\beta \in \mathbb{Q}(\alpha)$, and in that case I would like to represent $\beta$ in $\mathbb{Q}(\alpha)$, i.e. writing $\beta$ as a polynomial of $\alpha$ with rational coeffitiens.

Solution 1:

There are a few algorithms for such. First, one can apply LLL to find a witness to $\,\Bbb Z$-linear dependence of $\,\beta,1,\alpha,\alpha^2,\ldots,\alpha^{n-1}\,$ and, if found, then verify it using polynomial arithmetic. Alternatively, one can factor the minimal polynomial of $\,\beta\,$ over $\,\Bbb Q(\alpha)\,$ and check numerically if any linear factors correspond to $\,\beta.\,$ Factoring polynomials over $\,\Bbb Q(\alpha)\,$ reduces to factoring over $\,\Bbb Q[x]\,$ by taking gcds with the norm (algorithm of Pohst-Zassenhaus/Trager). For further details see for example section $4.5$ in H. Cohen, A course in computational algebra number theory.