Next: Fast Polynomial Multiplication based on

Foundations of Computer Algebra:
Fast Polynomial Multiplication

Marc Moreno Maza
University of Western Ontario
CS 424 / CS 556 - Winter 2006

Date: January 10, 2007

Fast Polynomial Multiplication based on the Discrete Fourier Transform

Primitive roots of unity
The Discrete Fourier Transform
Convolution of polynomials
The Fast Fourier Transform
Fast Convolution and Multiplication

Computing primitive n mathend000#-th roots of unity

Some results from group theory
Primitive n mathend000#-th roots of unity of finite fields
A Probabilistic Approach

Efficient implementation

Towards an iterative algorithm for the DTF

Bibliography
About this document ...

Next: Fast Polynomial Multiplication based on
Marc Moreno Maza
2007-01-10

Foundations of Computer Algebra: Fast Polynomial Multiplication

Foundations of Computer Algebra:
Fast Polynomial Multiplication