3-prime FFT

[Niels Möller]

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