Given two algebraic conjugates $\alpha,\beta$ and their minimal polynomial, find a polynomial that vanishes at $\alpha\beta$ in a efficient way
I don't see that the assumption that $\alpha$ and $\beta$ are roots of the same polynomial is particularly helpful. Suppose they have minimal polynomials $f(\alpha), g(\beta)$. Write down the companion matrices of these polynomials, then the Kronecker product of these matrices, then compute the characteristic polynomial of the Kronecker product. This polynomial isn't guaranteed to be irreducible, but from here you can factor it.