Longer NTT´s with 2 as a root of unity

When the specialized hardware is not too severe a constraint, the most promising Number Theoretic Transforms are those with 2 as a root of unity, since they can be performed without multiplication. Unfortunately, for a given wordlength, previously known NTT\´s with 2 as a root of unity are too short ( ) or too long (3.2ⁿ+ 1). It is then important to match the modulus of the transforms to the dynamic range of the convolution to be performed. To this end, we propose : - New NTT\´s (by the fact, new moduli) allowing longer transforms than those modulo or , these moduli being obtained through evaluations of generalized cyclotomic polymonials. -An "optimal" algorithm, which further enlarges the possible convolution length.