# 3-prime FFT

**Torbjorn Granlund
**
tege@swox.com

*14 Dec 2002 14:34:23 +0100*

Guillermo Ballester Valor <gbv@oxixares.com> writes:
I'm thinking that because for 64-bit machines and two primes,
we can achieve big basecases with big FFT runlengh. In a 32-bit
case it is not true.
I am afraid I don't understand this.
Then the CRT is more complicated than in the two-prime case,
and also don't forget we also need to do three FFT-based mul
instead of two although the small prime one were a lot faster.
We just need O(n) CRT operations, so that isn't the biggest
problem. But we should almost surely use just two primes for
operands, at least under a certain size.
Hum, for so small size (16 bits) it would be hard to find
primes with the propierties one usally wants (I'm thinkinig in
triplet/pair of primes p such as p-1 is divisible by k*2^j, k
usually a small prime 3,5 or 7 for non_power_of_two FFTS).
0xA001 with primitive root 3 would allow transform sizes up to
2^13.
But the more I think about it, the more I suspect we want to use
just two primes, and then as large as possible.
--
Torbjörn