Fast multiplication over algebraic number fields

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2011-12-01
Authors/Contributors
Author: Ahn, Cory
Abstract
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.
Document
Identifier
etd6911
Copyright statement
Copyright is held by the author.
Permissions
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
Attachment Size
etd6911_CAhn.pdf 937.47 KB