From Newton to Hensel

**Marc Moreno Maza
University of Western Ontario
AM583 - Fall 2003**

*Date:* 27 April 2004

- 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

- P-adic Expansions and Approximations
- Symbolic Newton Iteration

- Hensel Lifting

- Bibliography
- About this document ...

2004-04-27