A Modular Algorithm to Compute the Resultant of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions

Let \(f_1\) and \(f_2\) be two multivariate polynomials over an algebraic number field \({\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\) . In this paper, we present MRES, a modular algorithm for computing the resultant of \(f_1\) and \(f_2\) . To enhance the efficiency, our algorithm converts \(f_1\) and \(f_2\) to their corresponding polynomials over \(\mathbb {Q}(\gamma )\) where \(\gamma \) is a primitive element of \( {\mathbb {Q}(\alpha _1,\ldots ,\alpha _n)}\) . This conversion is done modulo a prime to prevent the coefficient growth. Next, our algorithm employs evaluation and dense interpolation to reduce the problem to the computation of the resultant of two univariate polynomials where we apply the monic Euclidean algorithm. Employing the monic Euclidean algorithm, we present a new formula for computing the resultant of univariate polynomials. Finally, our modular algorithm applies the Chinese remaindering and the rational number reconstruction to recover the rational coefficients of the resultant. We have implemented our algorithm in Maple. We include the expected time complexity of the algorithm, two benchmarks, and a partial failure probability analysis.