Implementing a Number Theoretic Transform (Fermat number transform--257). Should I consider alternatives to a radix-4 cooley-tukey?

This is kind of a comp sci question, but I figured I could use some input from FFT experts.

I've already got a radix-4 cooley-tukey implementation of the NTT briefly described on page 9-10 of https://who.rocq.inria.fr/Gaetan.Leurent/files/SIMD.pdf

which was pretty convenient when it came to putting together an Sse2 implementation (parallel computations of 4 32-bit unsigned integers instead of 1 at a time).

In the interest of squeezing out every last bit of efficiency for repeated runs, however, should I consider an alternate FFT implementation (Bruun's algorithm, for instance)? If you need more context to answer this, I'll be happy to provide more, this is the first time I've ever had to implement an FFT and I'm not sure what information is important. I'd also appreciate any further explanation you can provide; my understanding is still pretty shallow.

• I guess that by "Number Theoretic Transform" you mean that all calculations are done modulo 257 (GF-257) !? And what length of FFT's do you need? – Jens Apr 19 '15 at 12:10
• That's correct, yes. The output is of length 256 and the input is effectively of length 64 (technically 128, but the second half is just padded with zeroes. The input to the function itself is 16 unsigned 32bit integers, of which I'm using each byte separately). – MNagy Apr 19 '15 at 16:21
• I'm not sure how you transform a sequence of length 128 (including zero padding) to an output of 256. Also I'm not sure exactly how the 64 input values are represented by 16 unsigned 32bit integers. Each input requires slightly more than 8 bits. – Jens Apr 20 '15 at 20:55