# 3-prime FFT

**Torbjorn Granlund
**
tege@swox.com

*14 Dec 2002 23:00:16 +0100*

nisse@lysator.liu.se (Niels Möller) writes:
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)
I think we need primes, and of a special form to have high order roots
of unity.
--
Torbjörn