Next: Division with remainder using Newton Up: Efficient implementation Previous: Efficient implementation

## Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let n = 2r be a power of 2, let R be a primitive n-th root of unity and A(x) =  ai xi. 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](x2) + x A[1](x2) (52)

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

 ()2  =  ()2 (53)

This shows

 =   - (54)

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

 1,,,..., (55)

which allows us to evaluate A at

 1,,,..., (56)

Then to compute at A at

 ,,..., (57)

we use the fact these numbers are respectively equal to

 -1, - , - ,..., - . (58)

Algorithm 3

The recursive calls of DFT(n, A,) 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.

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 [a0, a4, a2, a6, a1, a5, a3, a7], 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 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 [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 ck of xk in f g is given by

 | ck |    (k + 1) | | f | | | | f | | (63)

• Let M be the biggest value of these bounds. Let p1,..., pr be primes such
• 2d divides each p1 - 1,..., pr - 1
• the product of p1,..., pr is bigger than 2 M.
• Then we can compute f g in each of the /pi[x] using the FFT-based multiplication.
• Finally we can recombine these modular product by applying the CRA to each coefficient ck (of xk) in f g.

Next: Division with remainder using Newton Up: Efficient implementation Previous: Efficient implementation
Marc Moreno Maza
2004-04-27