From Newton to Hensel

**Marc Moreno Maza
University of Western Ontario
CS874b - Winter 2002**

*Date:* 6 June 2003

- 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*-th roots of unity

- Efficient implementation

- Division with remainder using Newton iteration
- Classical division with remainder
- The quotient as a modular inverse
- Modular inverses using Newton iteration
- Division with remainder using Newton iteration

- Hensel Lifting
- Solving polynomial equations via Newton iteration
- Bibliography
- About this document ...

2003-06-06