**
**

Fast Polynomial Multiplication

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

**Date:** January 7, 2008

*
*

*
*

*
*

*
*

- 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
-th roots of unity
- Some results from group theory
- Primitive -th roots of unity of finite fields
- A Probabilistic Approach

- Efficient implementation

- Bibliography
- About this document ...

2008-01-07