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
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
