A novel combination of NTTs using the MRC

In this paper it is shown how the Fermat number transforms can be combined, using the mixed radix conversion, with a recently developed transform based upon the Mersenne numbers. The resulting combination uses fast small residue transforms which can be implemented in parallel for high speed and high throughput rate. The novel feature of the method is that it allows the combination of the Fermat and Mersenne number based transforms with their moduli selected to be conveniently close to one another, thus making more efficient use of the hardware/software than has previously been possible. The technique is suitable for the calculation of convolutions and correlations and leads to increased dynamic range and to the convenient use of parallel operation. Also this approach has the advantage that all arithmetic operations are carried out modulo the Mersenne and Fermat numbers, which are known to yield simple arithmetic.