New mulmod_bknp1

[Marco Bodrato]

Ciao,

Il 2022-02-21 01:37 Torbjörn Granlund ha scritto:
> I am too busy to examine the code to see what you've done.  Perhaps you
> could outline the algorithms here?

Nothing special...
Simply, if a multiplication mod B^{3n}+1 is needed, the code computes
  - a product mod B^{n}+1
  - a product mod B^{2n}-B^{n}+1
  - with CRT, the desired result is obtained.

This is generalised for multiplications mod B^{kn}+1 for k in 
{3,5,7,13,17}.

> Is n = 3^t-k now slower than n' = 3^t for small k (with k mod 3 != 0)?

Yes. But that's true for the product mod B^n+1.

> Then we could zero-pad such operands...

If a product mod B^64-1 is required to mulmod_bnm1, then the function 
computes two multiplications: mod B^32-1, and mod B^32+1.
Computing a product mod B^33+1 is now faster than computing mod 
B^32+1...
...but the product mod B^33+1 is simply not useful, the calling function 
needs the result mod B^32+1!

Ĝis,
m