fft interface

[Niels Möller]

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

> several applications using GMP (in particular GMP-ECM) use the internal fft
> functions (mainly mpn_mul_fft and mpn_fft_best_k) for multiplication modulo
> 2^N+1. This saves a factor of two with respect to mpn_mul_n if for example you
> know the lower part of a N-bit product, and you want to compute the upper part.

Internally in gmp, these days the function used for wraparound
arithmetic is mpn_mulmod_bnm1 (and mulmod_bnm1_next_size). Which
computes modulo B^n - 1, and is useful also below the fft threshold.
Have you tried that?

> However those functions are still internal. Is it planned in the future to
> make them (or similar functions) part of the public interface?

For the wraparound trick, I think something like mulmod_bnm1 is more
suitable for a public interface than the fft functions. Not sure if the
current interface is mature enough to qualify.

And we totally lack interfaces for invariance (and such interfaces don't
have to be fft-specific).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.