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 $n$ be a non-negative integer. Let $g \in R[x]$ be a polynomial of degree less than $n$ and let $f \in R[x]$ be a polynomial of degree less than $2n$ . 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 $R$ for computing $g^2 \mod{x^{2n}}$ .
2. Using classical arithmetic what is the number of operations in $R$ for computing $f g^2 \mod{x^{2n}}$ .
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 $R[x]$ with respective degrees $m$ and $n$ , assuming that $m -n + 1$ is a power of $2$ .
5. Compare with classical division.

Answer 3  

Answer 4  

Answer 5  

Answer 6