Unusual-length number-theoretic transforms using recursive extensions of Rader´s algorithm

A novel decomposition of NTT block-lengths is proposed using repeated applications of Rader´s (1968) algorithm to reduce the problem to that of realising a single small-length NTT. An efficient implementation of this small-length NTT is achieved by an initial basis conversion of the data, so that the new basis corresponds to the kernel of the small-length NTT. Multiplication by powers of the kernel become rotations and all arithmetic is efficiently performed within the new basis. More generally, this extension of Rader´s algorithm is suitable for NTT or DFT applications where an efficient implementation of a particular small-length NTT/DFT module exists