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.

- Using classical arithmetic what is the number of operations in for computing .
- Using classical arithmetic what is the number of operations in for computing .
- Deduce a (sharp) upper bound for the algorithm recalled on the first page.
- 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 . - Compare with classical division.

2008-01-31