Number-theoretic transforms with 2 as a root of unity

The letter is an attempt to generalise the advantageous features of Fermat number transforms to match the word length of the modulus of the NTT to the desired dynamic range of the convolution. First, a characterisation of all the transforms with x = 2 and N = 2n is given. We then extend the method to the case N = s × 2n.