A decomposition of the arithmetic for NTT's with 2 as a root of unity
Pierre Duhamel, Henk D. L. Hollmann · 2005
The most promising Number Theoretic Transforms are those with 2 as a root of unity, since they can be performed without multiplications. One of the main problems is then the complexity of the arithmetic modulo M. We present here a generalized form of the NTT allowing the study of the problems of the NTT's and their arithmetic modulo M together. We show that, among one class of NTT's (the moduli being obtained by evaluation of cyclotomic polynomials) there are some relations between the arithmetics involved, that can be used to decompose the "difficult" arithmetics into simpler ones (just like a DFT of length N1N2, (N1,N2) = 1 can be decomposed into several DFT's of length N1and N2). We also point out a possible application to polynomial transforms.