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.

Scholarly level

Supervisor or Senior Supervisor

Thesis advisor: Monagan, Michael

Member of collection

Download file | Size |
---|---|

etd6911_CAhn.pdf | 937.47 KB |