3-prime FFT

Guillermo Ballester Valor gbv@oxixares.com
Sat, 14 Dec 2002 22:39:48 +0100

On Saturday 14 December 2002 22:15, Niels M=F6ller wrote:
> 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).

This is true for CRT requirements. But we also need to make numerical=20
transforms, and I think it is only possible with true primes.


Guillermo Ballester Valor
Ogijares, Granada  SPAIN