Inspired by this question, I was wondering about the following problem.
$\alpha,\beta,\gamma,\ldots$ are the roots of an irreducible polynomial over $\mathbb{Q}$. How to compute the coefficients of $$ (x-\alpha\beta)(x-\alpha\gamma)\cdot \ldots\cdot (x-\beta\gamma)\cdot\ldots, $$ i.e. the candidate minimal polynomial of $\alpha\beta$, in the most efficient way?
My approach is based on a simple lemma and a general fact. If $p_m$ is the power sum $\alpha^m+\beta^m+\gamma^m+\ldots$ and $e_i$ is the $i$-th elementary symmetric polynomial, the identity $$ \exp\left(-\sum_{m\geq 1}\frac{p_m}{m}x^m\right) = \sum_{r\geq 0}(-1)^r e_r\,x^r$$ gives a way to compute $p_1,p_2,p_3,\ldots$ from $e_1,e_2,e_3,\ldots$ through the Taylor series of a logarithm ($\text{LOG}$) as well as $e_1,e_2,e_3,\ldots$ from $p_1,p_2,p_3,\ldots$ through the Taylor series of an exponential ($\text{EXP}$). Moreover, the characteristic polynomial of the sequence $\{p_k\}_{k\geq 0}$ is exactly the minimal polynomial of $\alpha$, hence we may compute $p_{n+1},p_{n+2},\ldots,p_{n+m}$ from $p_1,p_2,\ldots,p_n$ with a simple recursive approach (I will call this procedure $\text{CH}$, from Cayley-Hamilton). $\text{L}$ will be my previously mentioned lemma, i.e. $$ p_k(\alpha\beta,\alpha\gamma,\ldots) = \frac{1}{2}\left(p_k^2-p_{2k}\right).$$ Now my algorithm goes as follows:
(1). $$ e_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}\quad\xrightarrow{\text{LOG}}\quad p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}$$ (2). $$ p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n}\quad\xrightarrow{\text{CH}}\quad p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n(n-1)}$$ (3). $$ p_i(\alpha,\beta,\gamma,\ldots)_{i\leq n(n-1)}\quad\xrightarrow{\text{L}}\quad p_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}$$ (4). $$ p_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}\quad\xrightarrow{\text{EXP}}\quad e_i(\alpha\beta,\alpha\gamma,\ldots)_{i\leq \binom{n}{2}}.$$
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.