*
*

*
*

(9) |

It follows that is a multiple of . By repeating the same argument we show that . Then by induction on we obtain .

*
*

*
*

(10) |

(11) |

*
*

*
*

(12) |

(13) |

*
*

*
*

(14) |

For the induction step we have

(15) |

Indeed means that divides . Thus divides .

*
*

*
*

- Classical: ;
- Karatsuba: with some that can be taken equal to ;
- FFT over an arbitrary ring: for some that can taken equal to [CK91].

*
*

*
*

*
*

*
*

(17) |

Indeed, by virtue of Theorem 1 we have

(18) |

Therefore when computing we only care about powers of in the range . This says that

- half of the computation of
is made
during the last iteration of the
**for**loop, - a quater is made when computing etc.

(19) |

So

- two multiplications of polynomials with degree less than ,
- a multiplication of a polynomial (with degree less than ) by a constant,
- truncations modulo
- a subtraction of polynomials with degree less than .

The cost for the -th iteration is

- for the computation of ,
- for the product ,
- and then the opposite of the upper half of modulo (which is the upper half ) takes operations.

since for all

*
*

*
*

(21) |

*
*

*
*

*
*

*
*

(22) |

(23) |

(24) |

(25) |

*So let us assume from now on that we have at hand
a primitive
-th root of unity, such that we can
compute DFT's.
Therefore, we can compute
at the cost of one
multiplication in degree less than
.
*

*Consider now that we have computed
.
Viewing
and
as polynomials
with degrees less than
and
respectively,
there exist polynomials
with degree less
than
such that
*

(26) |

(27) |

*It follows that, in the complexity analysis above
(in the proof of Theorem 2)
we can replace
by
leading to
instead of
.
*

*
*

2008-01-07