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).
/Niels
More information about the gmp-devel
mailing list