Wraparound multiplicaton vs mullo

Niels Möller nisse at lysator.liu.se
Thu Oct 15 16:54:43 CEST 2009

Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:

>>   m = a 2^k + 1,  and prime
> However I don't see how your second example works, i.e., what w you
> take.

There's no simple formula, but the order of the multiplicative
subgroup is a 2^k, and hence there exists an element of order 2^k
(iirc, Sylow group is the related group theoretic concept). So you
have to search for w, probably the procedure is also related to a
miller-rabin test for the primality of m. Anyway, you probably don't
want to do this online, but small-prime fft uses fixed primes of this
form where w and some other needed values are precomputed.

> The main reason is that we want that one forward transform followed
> by one backward transform gives the identity, up to a constant
> factor.

But that property is not essential for fft multiplication. All we need
is an efficient way to evaluate a polynomial in n points, and an
efficient inverse of that procedure. The the formard and inverse
procedures are identical is not required (and a practical
implementation they are usually separate in any case, unless you want
to explicitly permute the elements of the inverse to get them in the
"right" order).


More information about the gmp-devel mailing list