# 3-prime FFT

**Niels Möller
**
nisse@lysator.liu.se

*14 Dec 2002 22:15:58 +0100*

Torbjorn Granlund <tege@swox.com> writes:
>* We need two large primes (64-bit or close to 64-bit)
*>* and one smaller prime.
*
If I remember the CRT correctly, the moduli need to be coprime, but
it's *not* necessary that they be primes. So for example, you can use
any two distinct odd primes, and let the third modulo be a power of
two (2^BITS_PER_LIMB seems like a good choice).
And if possible, one should probably also choose odd primes of the
form 2^n ± 1. And again, they need not strictly be primes, only
coprime. So one choice of moduli is
2^32, 2^32+1, 2^16+1 (32 limbs, at most 2^16 limbs)
2^64, 2^64+1, 2^32+1 (64-bit limbs, at most 2^32 limbs)
/Niels