mpn_mulmod_bnm1

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  No immediate plans. To me, it seems stable enough, if documented
  together with mpn_mulmod_bnm1_itch and mpn_mulmod_bnm1_next_size.
  
We should integrate the small primes FFT code,
https://gmplib.org/repo/gcd-nisse/file/0d591aa7e02c/mpn/generic/mul_spfft.c
in the next major GMP release.  Perhaps this would make mpn_mulmod_bnm1
trickier to maintain (at least as a cutting-edge primitive)?

I must admit that I don't recall the exact operation of the small primes
code.  Each separate polynomial multiply should compute a convoluttion
as usually, and the CRT and evaluation in the limb base \beta) should
keep a meaningful result mod 2^m + c got c = 1 or c = -1 (if done
properly) around the m boundary.

I am not sure what needs to be done to get mul_spfft.c in shape for
general inclusion.  I suppose a bunch of assembly implementations of the
butterfly operations will be needed.  Something more?

To lower the bar for inclusion, we could keep it disabled by default,
and enable it only if some encouraging parameter is set in gmp-mparam.h.

Torbjörn
Please encrypt, key id 0xC8601622