Computing GCDs of Multivariate Polynomials over Algebraic Number Fields Presented with Multiple Extensions

Mahsa Ansari, Department of Mathematics, Simon Fraser Univeristy

Thursday August 17th, 11:00am, in AQ 5004.

Abstract:

Let L = ℚ(α₁,...,α_n) be an algebraic number field. We designed a modular gcd algorithm for computing the monic gcd, g, of two polynomials f1,f2 in L[x1,...,xk]. To improve the efficiency of our algorithm, we use linear algebra to find an isomorphism between L and ℚ(γ) where γ is a primitive element of L. This conversion is performed modulo a prime to prevent expression swell. Next, we use a sequence of evaluation points to convert the multivariate polynomials to univariate polynomials, enabling us to employ the monic Euclidean algorithm. We currently use dense interpolation to recover x2,...,xk in the gcd. In order to reconstruct the rational coefficients in g, we apply the Chinese remaindering and the rational number reconstruction. We present an analysis of the expected time complexity of our algorithm. We have implemented our algorithm in Maple using a recursive dense representation for polynomials.