Wraparound multiplicaton vs mullo

[Niels Möller]

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).

/Niels