(55) |

(56) |

(57) |

(58) |

(59) |

(60) |

(61) |

(62) |

- Formulas (63).
- If is a primitive -root of unity, with , then is a primitive -root of unity.

**Observe that if the input array
is sorted w.r.t. this
DFT ordering, one can describe easily the
recursive calls with a binary tree.
If this tree is traversed bottom-up, from left to right,
we are led to an iterative algorithm working in place!
For instance, for
, assuming that the input array
is
**

- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=
- :=

*
*

(64) |

(65) |

- Let
and
be two univariate polynomials in
.
We can assume that all their coefficients are positive.
Otherwise, we can restrict to this case by setting
(66)

where , , , are polynomials with positive coefficients and writing(67)

and computing the products , , and one after another. - Let
and
be the max-norms of
and
.
Let
be the degree of
.
For
a bound for the coefficient
of
in
is given by
(68)

- Let
be the biggest value of these bounds.
Let
be primes such
- divides each
- the product of is bigger than .

- Then we can compute in each of the using the FFT-based multiplication.
- Finally we can recombine these modular product by applying the CRA to each coefficient (of ) in .

*
*

*
*

2008-01-07