Fast multiplication over algebraic number fields

Let $K=\mathbb Q(\alpha_1,\alpha_2,\ldots, \alpha_t)$ be an algebraic number field of degree D over $\mathbb{Q}$, and let f and g be polynomials in K[x] of degrees at most n. Naively computing the product fg requires $\mathcal{O}(n^2D^2)$ arithmetic operations in $\mathbb{Q}$. We developed a more efficient algorithm that computes fg modulo a series of primes to avoid working with rationals, and uses the fast Fourier Transform. For each prime p, it also avoids working over multiple extensions by computing a primitive element of K modulo p, which can be done using linear algebra or resultants and gcds. Our algorithm requires $\mathcal{O}(D^3+D^2n+Dn\log{n})$ arithmetic operations in $\mathbb{F}_p$ for each prime p. We have implemented our algorithm in Maple and present some timings to demonstrate that there is good speed-up in practice.