UNUSUAL-LENGTH NUMBER-THEORETIC TRANSFORMS USING RECURSIVE EXTENSIONSOF RADERS ALGORITHM

A novel decomposition of NTT block-lengths is proposed using repeated applications of Rader's algorithm to reduce the problem to that of rea lising a single small-length NTT. An efficient implementation of this small-length NTT is achieved by an initial basis conversion of the dat a, 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 general ly, this extension of Rader's algorithm is suitable for NTT or DFT app lications where an efficient implementation of a particular small-leng th NTT/DFT module exists.