Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let n = 2^r be a power of 2, let $\omega$ $\in$ R be a primitive n-th root of unity and A(x) = $\Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ a_i xⁱ. We define

A[0](x)	=	a0 + a2x + a4x2 + ... + an-2xn/2-1
A[1](x)	=	a1 + a3x + a5x2 + ... + an-1xn/2-1

(51)

such that

A(x)  =  A^[0](x²) + x A^[1](x²) (52)

Hence evaluating A at 1,$\omega$,$\omega^{{2}}_{{}}$,...,$\omega^{{{n-1}}}_{{}}$ is reduced to evaluate A^[0] and A^[1] at 1,$\omega^{{2}}_{{}}$,$\omega^{{4}}_{{}}$,...,$\omega^{{{2n-2}}}_{{}}$. But this second sequence of values consists of two identical sequences of length n/2. Indeed for every integer k we have

$$\omega^{{{k+ n/2}}}_{{}} \omega^{{{k}}}_{{}}$$ (53)

This shows

$$\omega^{{{k+ n/2}}}_{{}} \omega^{{{k}}}_{{}}$$ (54)

Hence we only need to evaluate A^[0] and A^[1] at

$$\omega^{{2}}_{{}} \omega^{{4}}_{{}} \omega^{{{n-2}}}_{{}}$$ (55)

which allows us to evaluate A at

$$\omega \omega^{{2}}_{{}} \omega^{{{n/2-1}}}_{{}}$$ (56)

Then to compute at A at

$$\omega^{{{n/2}}}_{{}} \omega^{{{n/2+1}}}_{{}} \omega^{{{n-1}}}_{{}}$$ (57)

we use the fact these numbers are respectively equal to

$$\omega \omega^{{2}}_{{}} \omega^{{{n/2-1}}}_{{}}$$ (58)

Algorithm 3  

The recursive calls of DFT(n, A,$\Omega$) defines a ordering of the coefficients of A shown on Figure 1. Let us call this ordering the DFT ordering of A.

THIS PART REQUIRES PROCESSING COMPLETELY BY HAND THE CASE n = 8.

Figure 1: Recursive calls for n = 8.

Algorithm 4  

THE FORMULA FOR t IN THE ABOVE ALGORITHM NEEDS TO BE CHECKED.

Remark 8   To get the DFT ordering for A, that is [a₀, a₄, a₂, a₆, a₁, a₅, a₃, a₇], observe that this ordering changes

000, 001, 010, 011, 100, 101, 011, 111 (59)

to

000, 100, 010, 110, 001, 101, 110, 111 (60)

Remark 9   The ring $\mbox{${\mathbb Z}$}$ 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 f and g be two univariate polynomials in $\mbox{${\mathbb Z}$}$[x]. We can assume that all their coefficients are positive. Otherwise, we can restrict to this case by setting

  f  =  f⁺ - f^-    and    g  =  g⁺ - g^- (61)

  
  
  where f⁺, f^-, g⁺, g^- are polynomials with positive coefficients and writing

  f g  =  f⁺g⁺ + f^-g^- - f⁺g^- - f^-g⁺ (62)

  
  
  and computing the products f⁺g⁺, f^-g^-, f⁺g^- and f^-g⁺ one after another.
• Let | | f | | and | | f | | be the max-norms of f and g. Let d be the degree of f g. For k = 0 ^... d a bound for the coefficient c_k of x^k in f g is given by

  $$\leq$$ (63)

  
  

• Let M be the biggest value of these bounds. Let p₁,..., p_r be primes such
  • 2^d divides each p₁ - 1,..., p_r - 1
  • the product of p₁,..., p_r is bigger than 2 M.
• Then we can compute f g in each of the $\mbox{${\mathbb Z}$}$/p_i$\mbox{${\mathbb Z}$}$[x] using the FFT-based multiplication.
• Finally we can recombine these modular product by applying the CRA to each coefficient c_k (of x^k) in f g.