## Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let be a power of , let be a primitive -th root of unity and . We define

 (55)

such that we have

 (56)

Hence evaluating at is reduced to evaluate and at . But this second sequence of powers of consists of two identical sequences of length . Indeed, for every integer we have

 (57)

Since holds, we obtain

 (58)

Hence we only need to evaluate and at

 (59)

This provides us directly with the values of at

 (60)

and the values of at

 (61)

by using the fact these numbers are respectively equal to

 (62)

To summarize, for we have

 (63)

Algorithm 3

The validity of Algorithm 3 follows from the two following observations.
• Formulas (63).
• If is a primitive -root of unity, with , then is a primitive -root of unity.
Observe that the recursive calls of defines an ordering of the coefficients of shown on Figure 2 for . Let us call this ordering the DFT ordering of .

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

We obtain the desired result in using the following straigth-line program
1. :=
2. :=
3. :=
4. :=
5. :=
6. :=
7. :=
8. :=
9. :=
10. :=
11. :=
12. :=
13. :=
14. :=
15. :=
16. :=
17. :=
18. :=
19. :=
20. :=
21. :=
22. :=
23. :=
24. :=
25. :=
26. :=
27. :=
28. :=
29. :=
30. :=
31. :=
32. :=
33. :=
34. :=
35. :=
36. :=
37. :=
38. :=
39. :=
40. :=
41. :=
42. :=
43. :=
44. :=
45. :=
46. :=
47. :=
48. :=

Algorithm 4

Remark 8   To get the DFT ordering for , that is , observe that this ordering changes

 (64)

to

 (65)

Remark 9   The ring does not have any interesting roots of unity. In order to take advantage of the FFT-based multiplication one could use a modular approach as follows.
• 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 .

Marc Moreno Maza
2008-01-07