#### Exercise 2.

The goal of this exercise is to understand how the fast division with remainder is slow when the underlying polynomial multiplication is not fast.

Let be a non-negative integer. Let be a polynomial of degree less than and let be a polynomial of degree less than . For this exercise, we rely on classical quadratic'' polynomial multiplication. Hence, we ignore all the tricks (Karatsuba, FFT) learnt in class.

1. Using classical arithmetic what is the number of operations in for computing .
2. Using classical arithmetic what is the number of operations in for computing .
3. Deduce a (sharp) upper bound for the algorithm recalled on the first page.
4. Deduce a (sharp) upper bound for the (not so) fast division with remainder when applied to a pair of polynomials in with respective degrees and , assuming that is a power of .
5. Compare with classical division.