Skip to main content

Fast multiplication over algebraic number fields

Resource type
Thesis type
(Thesis) M.Sc.
Date created
Author: Ahn, Cory
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.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Monagan, Michael
Member of collection
Download file Size
etd6911_CAhn.pdf 937.47 KB

Views & downloads - as of June 2023

Views: 38
Downloads: 1