3-prime FFT

[Torbjorn Granlund]

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